1/19, 创建/序列化

Construct Binary Tree from Preorder and Inorder Traversal

• 递归 ✔️

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

• preorder = [1, (5, 2, 3), (4, 6, 7)]
• inorder = [(2, 5, 3), 1, (4, 7, 6)]
• postorder = [(2, 3, 5), (7, 6, 4), 1]

单独用preorder或者inorder array的位置信息得不到完全一样的树，要把两个array结合起来。
此外，和Convert Array/Linked list to a Binary tree一样，使用递归来创建树，创建的过程是:

• 建当前root
• 拆分array，建root.left/root.right

利用preorder array的顺序，确定先建哪个为root。而利用inorder array可以切出左右子树，从而确定下一层的root。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null 
           || preorder.length == 0 || inorder.length == 0) return null;

        return build(preorder, 0, inorder, 0, preorder.length);
    }

    private TreeNode build(int[] pre, int s1, int[] in, int s2, int len) {
        if (len <= 0) return null;
        if (len == 1) return new TreeNode(pre[s1]);

        int rootVal = pre[s1];

        int pos = s2;
        while (pos < in.length && in[pos] != rootVal) {
            pos++;
        }

        int leftLen = pos - s2;
        int rightLen = len - 1 - leftLen;

        TreeNode root = new TreeNode(rootVal);
        root.left = build(pre, s1 + 1, in, s2, leftLen);
        root.right = build(pre, s1 + leftLen + 1, in, pos + 1, rightLen);

        return root;
    }
}

1/2一遍AC。。

Construct Binary Tree from Inorder and Postorder Traversal

和上题一样，在postorder 找root value， 然后在inorder找root value所在的position，接着计算 左右子树的length，建树

note: inorder array start building tree with index 0 while postorder array start building tree with index post.length - 1。

class Solution:
    def buildTree(self, inorder, postorder):
        if not preorder or not inorder:
            return None

        root = TreeNode(postorder[-1])
        position = inorder.index(postorder[-1])

        root.left = self.buildTree(inorder[:position], postorder[:position])
        root.right = self.buildTree(inorder[position+1:], postorder[position:-1])

        return root

12/18复习注，再分析下这两题的思路:

首先，凭空建树一定要有root，而这两题的root都来自于array，所以关键是找到用哪个点作root。

观察发现，preorder和postorder都可以用来找root，一个是从array[0]，一个从array[-1]，对所有子树也是一样。

然后，利用这个root在inorder里找到相应的position，它把inorder数组划分成的左子树，根，和右子树，就是最后要创建的树。

而在preorder数组里，这个position形成的三个区域，分别对应了根，左子树，和右子树。

和convert array to BST相比，相同点是都要找root，不同的是对于convert array to BST，root出现在array的每一个中点位置，而这两题的root都来自于traversal array。其次，对于convert array to BST，找到root后直接把array对半分就是左右子树，而这两题要结合inorder array来确定左右子树。

Constuct Binary tree From PreOrder and PostOrder

we can just use indexes to refer to the subarrays of pre and post .

public TreeNode constructFromPrePost(int[] pre, int[] post) {
    if (pre == null || post == null ||
        pre.length == 0 || post.length == 0) 
    return null;

    return build(pre, 0, post, 0, pre.length);
}

private TreeNode build (int[] in, int s1, int[] post, int s2, int len) {
    if (len <= 0) return null;
    if (len == 1) return new TreeNode(in[s1]);

    int rootVal = in[s1];
    int loc = s2;
    while (loc < s2 + len && post[loc] != in[s1 + 1]) {
        loc++;
    }

    int leftLen = loc - s2 + 1;
    int rightLen = len - leftLen - 1;

    TreeNode root = new TreeNode(rootVal);
    root.left = build(in, s1 + 1, post, s2, leftLen);
    root.right = build(in, s1 + leftLen + 1, post, s2 + leftLen, rightLen);

    return root;
}

Binary Tree Serialization

tree和string的相互转换。

序列化的思路是，正确做好单词的分隔还有分隔符的消除歧义，简单的可以就用()来区分左子树和右子树。明确root == null 的情形。在去序列化过程中，要注意找到左子树的最外层左右括号。

recursive method, similar to construction problems, 关键是要找左子树的左括号和右括号

public class Codec {

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

    private String build(TreeNode root) {
        if (root == null) {
            return "";
        }

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

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

        // TreeNode root = new TreeNode(data.charAt(0) - '0');
        int pos = data.indexOf("(");
        int val = Integer.parseInt(data.substring(0, pos));
        int indexFirstLeft = pos;

        pos++;
        int left = 1, right = 0;
        while (pos < data.length() && left != right) {
            if (data.charAt(pos) == '(') {
                left++;
            } else if (data.charAt(pos) == ')') {
                right++;
            }
            pos++;
        }
        int indexMatchingRight = pos - 1;

        TreeNode root = new TreeNode(val);
        root.left = deserialize(data.substring(indexFirstLeft + 1, indexMatchingRight));
        root.right = deserialize(data.substring(pos + 1, data.length() - 1));

        return root;
    }
}

iterative method using queue: serialize时，当 poll 的 node 是null，我就填充n，deserialize时，当不是n，我才处理和加到queue中

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("n ");
                continue;
            }
            sb.append(node.val + " ");
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return sb.toString();
    }

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

        Deque<TreeNode> q = new LinkedList<>();
        String[] values = data.split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        q.offer(root);

        for (int i = 1; i < values.length; i++) {
            TreeNode parent = q.poll();
            if (!values[i].equals("n")) {
                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                parent.left = left;
                q.add(left);
            }
            if (!values[++i].equals("n")) {
                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                parent.right = right;
                q.add(right);
            }
        }
        return root;
    }
}

note:

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