Star

Leetcode 331. Verify Preorder Serialization of a Binary Tree

Posted on | In |

Question:

One way to serialize a binary tree is to use pre-order 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 #. 

1
2
3
4
5
6
7
     _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: 

1
"9,3,4,#,#,1,#,#,2,#,6,#,#"

Return true

Example 2: 

1
"1,#"

Return false

Example 3: 

1
"9,#,#,1"

Return false

Explanation:

该怎么说呢，就是想破脑袋才想到stack做，再然后调了半天bug。如果遇到#，去检查是不是stack里面有一个#和一个阿拉伯数字，如果是的话，全部替换成一个“#”，表示一个子节点结束。最后判断是不是stack里只有一个“#”表示的根节点。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if(preorder== null) return false;
        Stack<String> stack = new Stack<>();
        String[] preorderGroup = preorder.split(",");
        for(String c:preorderGroup) {
            while(c.equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {
                stack.pop();
                if(stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
            stack.push(c);
        }
        if(stack.size()== 1 && stack.peek().equals("#")) return true;
        return false;
    }
}