106. Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

My Solutions:

1。recursive

根据postorder(left-right-root)和inorder(left-root-right)的特点，可以得到以下规律：

• 初始的时候，root 在postorder array的最末端(postE)，postE代表postorder array里最后一个元素

• 因为树里所有的元素都不同，可以通过val在inorder array里找到root的index

• root's right 在postorder array里root的前一个位置(postE-1) 。并且一定在inorder array里root的后方，换句话说，inorder array里root的右边都是右边的树，root将inorder array 一分为二。所以此时的inS(代表inorder的起始位置）是index+1, 此时的inE(代表inorder的终点位置）还是inE。

• root's left一定是在inorder array里root的前方，换句话说，inorder array里root的左边都是左边的树，root将inorder array 一分为二。所以此时的inS(代表inorder的起始位置）还是inS, 此时的inE(代表inorder的终点位置）是index-1。

  • 最复杂的就是此时postE应该是什么。root's left一定是在postorder array 里root的前方， 并且是所有右边树的前方。

  • （inE - index ）: 是此时root右边的所有节点的个数

  • 此时的postE是此时的root在postorder array里的位置。因此在post order里，root's left 会在现在postE减去此时root右边的所有节点的个数，再多减1（root本身）

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0) return null;
        return helper(postorder.length - 1, 0, inorder.length - 1, inorder, postorder);
    }
    
    public TreeNode helper(int postE, int inS, int inE, int[] inorder, int[] postorder) {
        
        if (postE < 0 || inS > inE) return null;
        
        TreeNode root = new TreeNode(postorder[postE]);
        
        int index = 0; //index of root in inorder
        for (int i = inS; i <= inE; i++) {
            if (inorder[i] == root.val) index = i;
        }
        
        //the right child of root is the root's prev in postorder, and must be in the root's right side in the inorder
        root.right = helper(postE - 1, index + 1, inE, inorder, postorder); 
        
        //the left child of root is among the root's prev in postorder, 
        //so that the postE = postE(index of current root in postorder) - 1 - (inE - index : the number of nodes on the right of current root)
        //and must be in the root's left side in the inorder
        root.left = helper(postE - 1 - (inE - index), inS, index - 1, inorder, postorder); 
        
        return root;
        
    }
}

2。iterative

对于一个root来说，root将inorder array一分为二。因此，先存一个inorder array's (value : index) in a map。用stack先存一个root，然后把postorder 里的数字从后往前遍历，建造节点node。如果此时value的index

• 大于 stack.peek的节点的index，说明当前node是peek到的数字的右节点。连上节点。最后把当前node塞入stack

• 小于 stack.peek的节点的index，说明当前node在某个节点的左边。为了找到当前node的root，一直pop stack同时保存弹出来的node，直到peek看到节点index 不再比当前index大。最后保存的那个节点就是当前的root。连上节点。最后把当前node塞入stack

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0) return null;
        
        // save inorder array's (value : index) in a map
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i); 
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        stack.push(root);
        
        for (int i = postorder.length - 2; i >= 0; i--) {
            int value = postorder[i];
            TreeNode node = new TreeNode(value); // 这个node是一个root
            
            if (map.get(value) > map.get(stack.peek().val)) { // node should be on the right of stack's top node
                stack.peek().right = node;
            } else { //node should be on the left of stack's top node
                TreeNode parent = null;
                while (!stack.isEmpty() && map.get(value) < map.get(stack.peek().val)) { //keep poping up node until find the root of current node && node should be on the left of stack's top node
                    parent = stack.pop();
                }
                parent.left = node;
            }
            stack.push(node); 
        }
        return root;
    }