331. Verify Preorder Serialization of a Binary Tree

Description

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

tree

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:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution

Stack, time O(n), space O(n)

用stack存储非空节点的还需要的左右节点个数。

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.isEmpty()) {
            return false;
        }
        
        String[] arr = preorder.split(",");
        if ("#".equals(arr[0])) {
            return arr.length == 1;
        }
        
        Stack<Integer> stack = new Stack<>();
        stack.push(2);
        
        for (int i = 1; i < arr.length; ++i) {
            if (stack.empty()) {
                return false;
            }

            int need = stack.pop().intValue() - 1;
            if (need > 0) {
                stack.push(need);
            }
            
            if ("#".equals(arr[i])) {
                continue;
            }
            
            stack.push(2);
        }
        
        return stack.empty();
    }
}

Indegree & Outdegree, time O(n), space O(1)

其实根据上面的思路，完全可以不用Stack，维护一个int diff即可。

实际上这利用的是Tree的特性，除root节点外：

• 任何一个非空节点都有2 outdegree和1 indegree
• 任何一个空节点都有1 indegree

注意diff初始化为1，可以理解成root节点有一个隐形的parent，parent的in为0，out为1。这样就不需要在循环前单独处理root节点了。

class Solution {
    public boolean isValidSerialization(String preorder) {
        int diff = 1;   // outdegrees - indegrees
        
        for (String s : preorder.split(",")) {
            if (--diff < 0) {   // minus one indegrees
                return false;
            }
            if (!"#".equals(s)) {   // non-null node
                diff += 2;      // add two outdegrees
            }
        }
        
        return diff == 0;
    }
}