[leetcode] problem 331 – verify preorder serialization of a binary tree

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  
/  /    / 
# # # #   # #

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

No.2

No.3

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public boolean (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 (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;
}