106. 从中序与后序遍历序列构造二叉树

/**
 * 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) {
        int postlength = postorder.length;
        int inlength = inorder.length;
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < inlength; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(postorder, 0, postlength - 1, map, 0, inlength - 1);
    }
    public TreeNode buildTree(int[] postorder, int postLeft, int postRight, Map<Integer, Integer> inorder, int inLeft, int inRight) {
        if (postLeft > postRight || inLeft > inRight) {
            return null;
        }
        int val = postorder[postRight];
        int pIndex = inorder.get(val);
        TreeNode root = new TreeNode(val);
        root.left = buildTree(postorder, postLeft, postRight - pIndex + inLeft - 1, inorder, inLeft, pIndex - 1);
        root.right = buildTree(postorder, postRight - pIndex + inLeft, postRight - 1, inorder, pIndex + 1, inRight);
        return root;
    }
}