#889根据前序和后序遍历构造二叉树

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if (preorder.length != postorder.length) {
            throw new IllegalArgumentException("Traversal lengths differ");
        }
        Map<Integer, Integer> postIndex = new HashMap<>();
        for (int i = 0; i < postorder.length; i++) postIndex.put(postorder[i], i);
        return build(preorder, 0, preorder.length - 1,
                postorder, 0, postorder.length - 1, postIndex);
    }

    private TreeNode build(int[] preorder, int preLeft, int preRight,
                           int[] postorder, int postLeft, int postRight,
                           Map<Integer, Integer> postIndex) {
        if (preLeft > preRight) return null;
        TreeNode root = new TreeNode(preorder[preLeft]);
        if (preLeft == preRight) return root;
        int leftRootIndex = postIndex.get(preorder[preLeft + 1]);
        int leftSize = leftRootIndex - postLeft + 1;
        root.left = build(preorder, preLeft + 1, preLeft + leftSize,
                postorder, postLeft, leftRootIndex, postIndex);
        root.right = build(preorder, preLeft + leftSize + 1, preRight,
                postorder, leftRootIndex + 1, postRight - 1, postIndex);
        return root;
    }
}