Construct Binary Tree from Inorder and Postorder Traversal leetcode

题解：

这道题跟pre+in一样的方法做，只不过找左子树右子树的位置不同而已。 

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

对于上图的树来说，
        index: 0 1 2 3 4 5 6
     中序遍历为: 4 2 5 1 6 3 7
     后续遍历为: 4 5 2 6 7 3 1
为了清晰表示，我给节点上了颜色，红色是根节点，蓝色为左子树，绿色为右子树。
可以发现的规律是：
1. 中序遍历中根节点是左子树右子树的分割点。
2. 后续遍历的最后一个节点为根节点。

同样根据中序遍历找到根节点的位置，然后顺势计算出左子树串的长度。在后序遍历中分割出左子树串和右子树串，递归的建立左子树和右子树。

算法最终相当于一次树的遍历，每个结点只会被访问一次，所以时间复杂度是O(n)。而空间我们需要建立一个map来存储元素到下标的映射，所以是O(n)。
reference: http://www.cnblogs.com/springfor/p/3884035.html

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, map);
    }
    public TreeNode helper(int[] inorder, int instart, int inend, int[] postorder, int postart, int poend, HashMap<Integer, Integer> map) {
        if (instart > inend || postart > poend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[poend]);
        int index = map.get(root.val);
        root.left = helper(inorder, instart, index - 1, postorder, postart,  index - instart + postart - 1, map);
        root.right = helper(inorder, index + 1, inend, postorder, index - instart + postart, poend - 1, map);
        return root;
    }
}