One way to serialize a binary tree is to use pre-oder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as
#
._9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # #
For example, the above binary tree can be serialized to the string
"9,3,4,#,#,1,#,#,2,#,6,#,#"
, where #
represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character
'#'
representing null
pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as
"1,,3"
.
Example 1:
Return
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return
true
Example 2:
Return
"1,#"
Return
false
Example 3:
Return
A:"9,#,#,1"
Return
false
*******就是建立一个stack,来模拟深度,如果是visiting left child, 则stack上放1, 否则放 -1.
******************
每次看见一个 # ,表示结束了一个分支。 ********
**********直接一遍秒过,还不错,Tiger,明天犒劳自己*********
public class Solution { public boolean isValidSerialization(String preorder) { String[] A = preorder.split(","); Stack<Integer> stack = new Stack(); //1 for left, -1 if visiting right for(String cur : A){ cur = cur.trim(); if(! cur.equals("#")){ stack.push(1); }else{ while( ! stack.isEmpty() && stack.peek()<0){ stack.pop(); } if( !stack.isEmpty()){ stack.pop(); stack.push(-1); } } } return stack.isEmpty(); } }
No comments:
Post a Comment