331. Verify Preorder Serialization of a Binary Tree

• 看到数字，直接push到stack中

• 看到#，看当前栈顶是不是#：

  • 如果是：在while循环中pop#，每次pop两个值，因为左右两个子树，直到栈顶不再是#。最后push当前#到stack中。

  • 如果不是：直接push到stack中。

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

        Stack<String> stack = new Stack<>();
        String[] strs = preorder.split(",");

        for (int i = 0; i < strs.length; ++i) {
            String curr = strs[i];

            while (curr.equals("#") && !stack.isEmpty() && stack.peek().equals("#")) {
                stack.pop();
                if (stack.isEmpty()) return false;
                stack.pop();
            }

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

这题用stack做真的不好想，而且corner case很烦。贴一个简单的论坛解法。

如果null作为叶子节点的话，那么

• 每一个非空节点有2个出度和1个入度

• 每一个空节点有0个出度和1个入度

定义diff = 出度 - 入度

每来一个新节点，diff减1，因为每个节点都有一个入度。如果节点非空(!= "#")，diff加2，因为非空节点有2个出度。

最开始diff为1。因为根节点。这样的话，序列化正确的情况下，diff永远不小于0，最后结束时diff为0。

这个思路可以验 pre-order 与 post-order 的 serialization.

public class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] strs = preorder.split(",");
        int diff = 1;
        for (String str : strs) {
            if (--diff < 0) return false;
            if (!str.equals("#")) diff += 2;
        }
        return diff == 0;
    }
}

最后一个思路是，借鉴之前 Serialization 的 pre-order 重建法，保存 doLeft 的 boolean 变量模拟重建树的过程。当然，这里 stack 存的其实是一个 stack frame，而不再是具体 node，左右子树也不重要了。

    private class TreeNode{
        int val;
        public TreeNode(int val){
            this.val = val;
        }
    }

    public boolean isValidSerialization(String preorder) {
        if(preorder.equals("#")) return true;

        Stack<TreeNode> stack = new Stack<>(); 
        String[] strs = preorder.split(",");
        TreeNode root = (!strs[0].equals("#"))
                        ? new TreeNode(0)
                        : null;
        stack.push(root);
        boolean doLeft = true;

        for(int i = 1; i < strs.length; i++){
            // Multiple roots
            if(i != 0 && stack.isEmpty()) return false;
            if(stack.peek() == null) return false;

            String str = strs[i];
            TreeNode node = (str.equals("#"))
                            ? null 
                            : new TreeNode(0);

            if(doLeft){
                if(node == null) doLeft = false;
            } else {
                if(stack.isEmpty()) return false;
                stack.pop();
                if(node != null) doLeft = true;
            }
            if(node != null) stack.push(node);
        }

        return stack.isEmpty();
    }

341. Flatten Nested List Iterator

NestedInteger 是一种树状结构，其中每一个是 List 的元素代表一个三角形，下面有自己的子树。