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

Thoughts:

1. Similar to 105, but build the postidx from the back

2. The the basic idea is to take the last element in postorder array as the root, find the position of the root in the inorder array; then locate the range for left sub-tree and right sub-tree and do recursion. Use a HashMap to record the index of root in the inorder array.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(postorder, postorder.length - 1, inorder, 0, inorder.length -1);
    }
    private TreeNode build(int[] postorder, int posIdx, int[] inorder, int inStart, int inEnd){
        if(inStart > inEnd || posIdx < 0) return null;
        TreeNode root = new TreeNode(postorder[posIdx]);
        int i = 0;
        for(i = inStart; i <= inEnd; i ++){
            if(inorder[i] == postorder[posIdx]) break;
        }

        root.right = build(postorder, posIdx - 1, inorder, i + 1, inEnd); 
        root.left = build(postorder, posIdx - 1 - (inEnd - i), inorder, inStart, i - 1);
        return root;
    }
}

Code: with hashMap

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length)
        return null;

        HashMap<Integer, Integer> hm = new HashMap<Integer,Integer>();
        for (int i=0; i< inorder.length; ++i)
            hm.put(inorder[i], i);

        return buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1,hm);
}

private TreeNode buildTreePostIn(int[] inorder, int is, int ie, int[] postorder, int ps, int pe,              HashMap<Integer,Integer> hm){

    if (ps>pe || is>ie) return null;
    TreeNode root = new TreeNode(postorder[pe]);
    int i = hm.get(postorder[pe]);
    // i - is: number of nodes in the left subtree
    root.left = buildTreePostIn(inorder, is, i-1, postorder, ps, ps+i-is-1, hm);
    root.right  = buildTreePostIn(inorder,i+1, ie, postorder, ps+i-is, pe-1, hm);

    return root;

    }
}