创建 / 序列化

• 要学会用 continuous subarray 的眼光去看三序遍历数组，子树结构 = 子序列结构

• 对于任意指定子树，在 inorder / preorder / postorder 中都是长度一样的连续 subarray，只是位置不同。

Construct Binary Tree from Preorder and Inorder Traversal

这题挺常见的，而且在树类问题里我也很喜欢，很考察对于树的理解。

             [1] 
           /     \ 
         [5]      [4]
        /   \       \ 
      [2]   [3]      [6] 
                    /
                  [7]

• In-order: 【(2,5,3) 1 (4,7,6)】

• Pre-order: 【1 (5,2,3) (4,6,7)】

• Post-order: 【(2,3,5) (7,6,4) 1】

In-order 和 pre-order 单独都只能提供一部分树的信息，只依靠一个无法建立出完全一样的树，因为有歧义。

• In-order : 对于指定位置 index 的 root

  • 对于每个 tree / subtree, array 结构

  • 【左子树】【root】【右子树】

• Pre-order:

  • 对于每个 tree / subtree, array 结构

  • 【root】【左子树】【右子树】

• Post-order:

  • 对于每个 tree / subtree, array 结构

  • 【左子树】【右子树】【root】

递归建树的过程是

• 建当前 root;

• 建 左/右 子树；

• 建 右/左 子树；

因此根据 inorder 和 preorder 的性质，我们用 preorder 的顺序决定“先建哪个为 root”，用 inorder 的相对位置决定 “左右子树是谁”。

因此这个问题是关于 preorder 的遍历，对于每个元素要在 inorder 中寻找相对位置。

对于任意指定子树，在 inorder / preorder / postorder 中都是长度一样的连续 subarray，只是位置不同。

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int preorderIndex, 
                           int inorderStart, int inorderEnd){
        if(inorderStart > inorderEnd || preorderIndex >= preorder.length) return null;

        int rootVal = preorder[preorderIndex];
        int pos = inorderStart;
        for(int i = inorderStart; i <= inorderEnd; i++){
            if(inorder[i] == rootVal){
                pos = i;
                break;
            }
        }

        int leftSubTreeLength = pos - inorderStart;

        TreeNode root = new TreeNode(rootVal);
        root.left = build(preorder, inorder, preorderIndex + 1, inorderStart, pos - 1);
        root.right = build(preorder, inorder, preorderIndex + leftSubTreeLength + 1, pos + 1, inorderEnd);

        return root;
    }
}

同一题一个比较 pythonic 的解法甚至不需要像 java 一样定义区间

class Solution: 
    def buildTree(
        self, 
        preorder: List[int], 
        inorder: List[int]
    ) -> TreeNode: 
        return self.buildHelper(preorder, inorder)

    def buildHelper(
        self, 
        preorder: List[int], 
        inorder: List[int], 
    ) -> TreeNode:
        if len(preorder) == 0:
            return None
        if len(inorder) == 0:
            return None
        # create node 
    
        node = TreeNode(preorder.pop(0))
    
        in_order_index = inorder.index(node.val)
        in_order_len = len(inorder)
    
        # build left tree
        node.left = self.buildHelper(
            preorder, 
            inorder[0:in_order_index], 
        )
        # build right tree
        node.right = self.buildHelper(
            preorder, 
            inorder[in_order_index+1:], 
        )
    
        return node

Construct Binary Tree from Inorder and Postorder Traversal

掌握了这个性质之后，把 preorder 换成 postorder 也是一样的配方，一样的味道。

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int[] inorder, int[] postorder, int index, int inorderStart, int inorderEnd){
        if(inorderStart > inorderEnd || index < 0) return null;

        int rootVal = postorder[index];
        int pos = inorderStart;
        for(int i = inorderStart; i <= inorderEnd; i++){
            if(inorder[i] == rootVal){
                pos = i;
                break;
            }
        }

        int rightSubtreeLength = inorderEnd - pos;

        TreeNode root = new TreeNode(rootVal);
        root.left = build(inorder, postorder, index - rightSubtreeLength - 1, inorderStart, pos - 1);
        root.right = build(inorder, postorder, index - 1, pos + 1, inorderEnd);

        return root;
    }
}

Serialize and Deserialize Binary Tree

这也是个很有意思的问题，核心问题类似于 encode / decode strings，在于 “如何确定唯一的 binary tree ?” 对于 List of String 来讲，只需要正确做好单词的分隔还有分隔符的消除歧义；而 Tree 上可以有 level 的分隔，left / right subtree 的分隔。

相对来讲Tree的优势是，这个 TreeNode 里面只存数字，所以有很多额外的字母和符号可以利用，不用担心所用字符的歧义问题（不然就得定义 escape 符了）

http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/

• If given Tree is Binary Search Tree?

  If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.

• If given Binary Tree is Complete Tree?

  A Binary Tree is complete if all levels are completely filled except possibly the last level and all nodes of last level are as left as possible (Binary Heaps are complete Binary Tree). For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.

• If given Binary Tree is Full Tree?

  A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.

• How to store a general Binary Tree?

  A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree. We can save space by storing Preorder traversal and a marker for NULL pointers.

解决这题的关键就是，自己补位，构建一个 full binary tree 出来。

自己第一遍 AC 的代码。思想就是做 preorder ，不过把左右子树分别用括号括起来。空节点会生成空括号。这样对于一棵子树的 substring，第一个 matching 括号就代表左子树，后面的就是右子树。

这种写法的好处一是和这章之前的思想有联系和继承，第二是不需要用逗号做分隔（但是每个叶节点会生成一对空括号）

递归的时候注意抹去括号的 index 细节，并且在一开始检查下是不是 "()".

另外一个经验是，处理字符串的时候尽量直接用内置函数，比如 str.indexOf('x') 这种，知道题的重点不是字符串就别每次都手写了。

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";

        String left = serialize(root.left);
        String right = serialize(root.right);

        return Integer.toString(root.val) + "(" + left + ")" + "(" + right + ")";
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0) return null;
        if(data.equals("()")) return null;

        int indexFirstLeft = data.indexOf('(');
        int rootVal = Integer.parseInt(data.substring(0, indexFirstLeft));

        int leftCount = 1;
        int indexMatchingRight = indexFirstLeft + 1;

        while(indexMatchingRight < data.length() && leftCount != 0){
            if(data.charAt(indexMatchingRight) == '(') leftCount ++;
            if(data.charAt(indexMatchingRight) == ')') leftCount --;

            indexMatchingRight ++;
        }

        String leftSubtree = data.substring(indexFirstLeft + 1, indexMatchingRight - 1);
        String rightSubtree = data.substring(indexMatchingRight + 1, data.length() - 1);

        TreeNode root = new TreeNode(rootVal);
        root.left = deserialize(leftSubtree);
        root.right = deserialize(rightSubtree);

        return root;
    }
}

论坛上比较简洁正规的 pre-order DFS 递归写法：

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfsSerialize(root, sb);
        return sb.toString().trim();
    }

    private void dfsSerialize(TreeNode root, StringBuilder sb){
        if(root == null){
            sb.append("#").append(" ");
            return;
        }

        sb.append(root.val).append(" ");
        dfsSerialize(root.left, sb);
        dfsSerialize(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(" ");
        int[] index = new int[1];

        return dfsDeserialize(strs, index);
    }

    private TreeNode dfsDeserialize(String[] strs, int[] index){
        if(strs[index[0]].equals("#")){
            index[0]++;
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(strs[index[0]]));
        index[0]++;
        root.left = dfsDeserialize(strs, index);
        root.right = dfsDeserialize(strs, index);

        return root;
    }

另一种写法是 BFS，源代码是 LeetCode 论坛上的：

这个写法里会在 queue 里放入 null.

核心思想是，用 # 补位，构造一个 "full binary tree"，每个节点有 0 / 2 个子节点。因此在我们构造树的过程中，我们永远可以一次看两个元素，并且把子节点加入队列，保证算法的正确性。

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        StringBuilder res = new StringBuilder();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                res.append("#,");
                continue;
            }
            res.append(node.val + ",");
            q.add(node.left);
            q.add(node.right);
        }
        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == "") return null;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        String[] values = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        q.add(root);
        for (int i = 1; i < values.length; i++) {
            TreeNode parent = q.poll();
            if (!values[i].equals("#")) {
                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                parent.left = left;
                q.add(left);
            }
            if (!values[++i].equals("#")) {
                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                parent.right = right;
                q.add(right);
            }
        }
        return root;
    }
}

在 Binary Tree 的各种遍历中，BFS 都是比较耗费空间的一种，所以一个显然的优化与 follow up 就是，能不能用 DFS ，迭代做。

去论坛看了一圈，发现对于 full binary tree，pre-order 和 in-order 的 DFS 都行，挺有意思的~

这种做法其实就是一种对 pre-order DFS 做法的 Stack 模拟。也是 Tree 类问题递归转迭代的常用手段。

• 关键点1： 要存一个 boolean 记录下当前要填的点是不是左节点；

• 关键点2：这个 boolean 的变化要看当前 boolean 值以及新填上的点是不是叶节点；

• 关键点3：对于填充右节点的情况，链接完了就直接 pop()，有别于填充左子树时候用的 peek(). 因为 preorder 右子树结束之后 stack frame 就出栈了。

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        stack.push(root);

        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node == null){
                sb.append("#").append(" ");
                continue;
            }

            sb.append(node.val).append(" ");
            stack.push(node.right);
            stack.push(node.left);
        }
        return sb.toString().trim();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Stack<TreeNode> stack = new Stack<>();
        String[] strs = data.split(" ");
        if(strs[0].equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
        stack.push(root);
        int index = 1;
        boolean doLeft = true;
        while(index < strs.length){
            String str = strs[index++];
            TreeNode node = (str.equals("#")) 
                            ? null
                            : new TreeNode(Integer.parseInt(str));
            if(doLeft){
                stack.peek().left = node;
                if(node == null) doLeft = false;
            } else {
                stack.pop().right = node;
                if(node != null) doLeft = true;
            }

            if(node != null) stack.push(node);
        }
        return root;
    }

Verify Preorder Serialization of a Binary Tree

先贴个用自己理解写的做法：

Stack 里面存 node ，记录来路，对于每个 node，存一个 boolean 表示 “左子树处理完没”。这样当我们每次处理完一个 node 之后，都以栈顶为准，如果栈顶 boolean = false，就设成 true，代表左子树看完了，开始看右子树；否则就一路 pop 到第一个左子树没处理完的节点为止。

• corner case1: "#" 代表空树，合法；

• corner case2: stack 只能空一次，中间如果再出现 stack 为空然后往里加 node 的情况，说明是多个 root，返回 false;

public class Solution {
    private class Node{
        boolean isLDone;
        public Node(){
            isLDone = false;
        }
    }

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

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

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

            String str = strs[i];
            if(str.equals("#")){
                // Invalid leaf
                if(stack.isEmpty()) return false;
                Node top = stack.peek();
                if(!top.isLDone){
                    top.isLDone = true;
                } else {
                    while(!stack.isEmpty()){
                        stack.pop();
                        if(!stack.isEmpty() && !stack.peek().isLDone){
                            stack.peek().isLDone = true;
                            break;
                        }
                    }
                }
            } else {
                stack.push(new Node());
            }
        }

        return stack.isEmpty();
    }
}

另一种妖孽的写法是 dietpepsi 的 graph degree 思路，在这个帖子

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

• 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).

public boolean isValidSerialization(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.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();
    }