331. Verify Preorder Serialization of a Binary Tree

推荐Version #2

Version #4 Using stack [better version]
explanation直接看code里面的comment也可以
没有Version #3那么无脑，基本思路是一直的，就是一直砍leaf然后将它们的parent退化成新的leaf
速度比Version #3好一点点

用stack模拟了对tree的根-左-右traversal的操作
[1]如果是数字，就push
[2]如果是#，看一下它的上一个是不是#
  case1 上一个点是#： 证明走到了leaf, pop两次
                       可以保证不会出现#,#,#(curr)连续的情况，因为一旦有两个连续#就会进行pop操作，所以一定是x,#,#(curr)
                        pop之后(见[3])
  case2 上一个点不是#： 证明现在的'#'是一个node的left child -> push curr

[3]对于[2].case1，有两种情况
   case1 上一个点是#，证明当前的x,#,# -> # 将它的parent退化成了一个新的leaf, 可以继续pop
   case2 上一个点是node，证明当前的x,#,# -> #是一个left child，此时重新push一个“#”

一旦出现pop或者peek不出来的情况，就可以直接返回false了，证明之前没有traverse到足够的点与当前的点组成valid part
最后剩下的是一个“#”


"when you iterate through the preorder traversal string, for each char:

case 1: you see a number c, means you begin to expand a new tree rooted with c, you push it to stack

case 2.1: you see a #, while top of stack is a number, you know this # is a left null child, put it there as a mark for next coming node k to know it is being the right child.

case 2.2: you see a #, while top of stack is #, you know you meet this # as right null child, you now cancel the sub tree (rooted as t, for example) with these two-# children. But wait, after the cancellation, you continue to check top of stack is whether # or a number:

---- if a number, say u, you know you just cancelled a node t which is left child of u. You need to leave a # mark to the top of stack. So that the next node know it is a right child.

---- if a #, you know you just cancelled a tree whose root, t, is the right child of u. So you continue to cancel sub tree of u, and the process goes on and on."

 14.07 %
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) return true;
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        for (String curr : nodes) {
            if (!curr.equals("#")) {
                stack.push(curr);
            } else {
                // curr == "#" and it is a right child of a leaf node
                while (!stack.isEmpty() && stack.peek().equals("#")) {
                    stack.pop();
                    if (stack.isEmpty()) return false;
                    stack.pop();
                    //go back to the while loop to check if its a left child or a right child
                }
                // curr == "#" and it is a left child of a node
                //we still need to push it back to the stack
                stack.push(curr);
            }
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}



Version #3 Using stack
比较无脑的方法, 每次都push, 一看到leaf就往外pop
需要做stack.get()理论上来说是不属于stack这个数据结构的操作
version #4更elegant一点

Time O(#nodes)
Space O(#nodes)
4.56 %
//A leaf node must be "node", "#", "#"
//we can use a "#" to substitude the leaf node
//There will only be 1 "#" in the end
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) return true;
        String[] nodes = preorder.split(",");
        Stack<String> stack = new Stack<>();
        for (String node : nodes) {
            stack.push(node);
            while (stack.size() >= 3) {
                int size = stack.size();
                if (stack.get(size - 1).equals("#") && stack.get(size - 2).equals("#") && !stack.get(size - 3).equals("#")) {
                    for (int i = 0; i < 3; i++) {
                        stack.pop();
                    }
                    stack.push("#");
                } else break;
            }
        }
        return stack.size() == 1 && stack.peek().equals("#");
     
    }
}


Version #2

Count #nodes and #pound signs(null)

Eventually #Nodes + 1 == #("#")
For every moment, #Nodes + 1 >= #("#")
上面是算法哥讲的
判断依据是
Since it is a preorder traversal, the root nodes are always visited before their '#' children
所以node个数 + 1 一直是大于 pound sign个数，最后达到相等模糊
我觉得这个说法稍显模糊


LC上一个答案写的比较好
把二叉树看成一个directed graph
for every moment
    outdegree  >= indegree
otherwise we will have some hanging points

“In a binary tree, if we consider null as leaves, then

• all non-null node provides 2 outdegree and 1 indegree (2 children and 1 parent), except root
• all null node provides 0 outdegree and 1 indegree (0 child and 1 parent).

Suppose we try to build this tree. During building, we record the difference between out degree and in degree diff = outdegree - indegree. When the next node comes, we then decrease diffby 1, because the node provides an in degree. If the node is not null, we increase diff by 2, because it provides two out degrees. If a serialization is correct, diff should never be negative and diff will be zero when finished.”

一开始写是在每一个state结束以后判断outdegree-indegree < 0
有一个case跑不过

"#,7,6,9,#,#,#"

当7来的时候并没有indegree可以consum，所以应该在每个Node来的时刻判断

52.53 %
public class Solution {
    public boolean isValidSerialization(String preorder) {
        if (preorder == null || preorder.length() == 0) return true;
        //root doesn't have any indegree
        int indegree = -1;
        int outdegree = 0;
        String[] nodes = preorder.split(",");
        for (String curr : nodes) {
            //every coming node consumes 1 indegree
            indegree++;
            if (outdegree - indegree < 0) return false;
            if (!curr.equals("#")) outdegree += 2;        
        }
        return outdegree == indegree;
    }
}


Version #1 Reconstruct BST
实在懒得再写了
但是这个思路很值得学习