Construct Binary Tree from Inorder and Postorder Traversal

Leetcode

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

Analysis

1. post-order的最后一个作为root
2. 从in-order中找到root，左边range是left tree，右边range是right tree
3. post-order根据这两个range可以recursive的建立subtree

Code

public TreeNode buildTreePostIn(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 ri = hm.get(postorder[pe]);
    TreeNode leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);
    TreeNode rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);
    root.left = leftchild;
    root.right = rightchild;
    return root;
}

Notes

1. 用hashmap存inorder，因为要反复的从inorder中找root值的index。所以hashmap的key是inorder的value，value是inorder的index。
2. 这题的难点在于left和right tree的index的选择需要很小心，特别是postorder的index。
   1. Left tree： 在inorder里找到root的index ri以后，通过ri-is得到left tree的长度。postorder里取前ri-is个构成left tree。
      1. inorder: is -> ri-1
      2. postorder: ps -> ps+ri-is-1
   2. Right tree：
      1. inorder: ri+1 -> ie
      2. postorder: ps+ri-is -> pe-1

Reference

Leetcode