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

import java.util.*;

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

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

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

    private TreeNode build(int[] inorder, int inLeft, int inRight,
                           int[] postorder, int postLeft, int postRight,
                           Map<Integer, Integer> index) {
        // 中序区间为空时，对应子树为空；两个遍历区间必须同步收缩。
        if (inLeft > inRight) return null;
        // 后序区间末元素是当前根，中序位置决定左子树节点数。
        int rootValue = postorder[postRight];
        int pivot = index.get(rootValue);
        int leftSize = pivot - inLeft;
        TreeNode root = new TreeNode(rootValue);
        // 左右子树的后序边界按 leftSize 同步偏移，且排除根节点。
        root.left = build(inorder, inLeft, pivot - 1, postorder,
                postLeft, postLeft + leftSize - 1, index);
        root.right = build(inorder, pivot + 1, inRight, postorder,
                postLeft + leftSize, postRight - 1, index);
        return root;
    }
}