331 Verify Preorder Serialization of a Binary Tree

331. Verify Preorder Serialization of a Binary Tree

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

     _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'#'representingnullpointer.

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,#,#" Returntrue

Example 2:"1,#" Returnfalse

Example 3:"9,#,#,1" Returnfalse

2. Implementation

(1) Stack

思路: 这里用stack和利用stack做preorder traversal类似，可以分以下几种情况考虑:

1. 如果当前的node是数字，说明我们将以这个node作为根展开，将node push到stack

2. 如果当前的node是#,

2.1. 而栈顶是数字，说明当前的node代表的是left null child,我们将它放在stack上作为一个记号，这样接下来node就知道它自己是right child

2.2. 而栈顶是#，说明当前node是right null child, 这时我们至少call两次 stack.pop()，代表以node的parent作为根的subtree cancel，同时我们查看栈顶的是数字还是#

2.2.1. 如果栈顶是数字，说明我们刚刚将一个node t从栈顶弹出，而这个node t是一个left child, 这时我们需要将#留在stack里，作为记号，让后面的node知道它自己是right child

2.2.2 如果栈顶是#, 说明我们刚刚取消了一个以node t为根的subtree, 而node t是一个right child，所以我们继续将stack元素弹出

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) {
            return false;
        }

        String[] nodes = preorder.split(",");

        Stack<String> stack = new Stack<>();

        for (String node : nodes) {
            while (node.equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {
                stack.pop();

                if (stack.isEmpty()) {
                    return false;
                }

                stack.pop();
            }
            stack.push(node);
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

(2) Graph Property

思路: 这种解法利用了树的入度和出度是相同的性质。我们定义diff = Outdegree - Indegree, 对于每个node，其入度为1，所以diff也相应减1。而如果node不是#的话，出度为2，所以diff也相应加2。需要注意的是，我们将diff初始化为1,原因是我们将root也作为一个普通的node处理，然而root的入度是0， 出度是2，所以我们将diff初始化为1，这样root作为普通node，它的diff也是1

class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) {
            return false;
        }

        String[] nodes = preorder.split(",");

        int diff = 1;
        for (String node : nodes) {
            --diff;
            if (diff < 0) {
                return false;
            }
            if (!node.equals("#")) {
                diff += 2;
            }
        }
        return diff == 0;
    }
}

3. Time & Space Complexity

Stack: 时间复杂度O(n), 空间复杂度O(n)

Graph Property : 时间复杂度O(n), 空间复杂度O(1)