[LeetCode] Problem 331 - Verify Preorder Serialization of a Binary Tree

Posted on | In ,

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

No.1

Input: “9,3,4,#,#,1,#,#,2,#,6,#,#”

Output: true

No.2

Input: “1,#”

Output: false

No.3

Input: “9,#,#,1”

Output: false

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isValidSerialization(String preorder) {
    String[] str = preorder.split(",");
    Stack<String> stack = new Stack<>();

    for (int i = str.length - 1; i >= 0; i--) {
        if (!str[i].equals("#")) {
            if (stack.size() < 2)
                return false;
            
            stack.pop();
            stack.pop();
        }

        stack.push(str[i]);
    }

    return stack.size() == 1;
}

Other

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isValidSerialization(String preorder) {
    String[] str = preorder.split(",");
    int degree = 1;

    for (int i = 0; i < str.length; i++) {
        degree--;

        if (degree < 0)
            return false;

        if (!str[i].equals("#"))
            degree += 2;
    }

    return degree == 0;
}