#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<>();
        // 值唯一时，索引表可在 O(1) 时间定位左子树根。
        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]);
        // 单节点区间没有子树，也不能再访问 preLeft + 1。
        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;
    }
}