#105从前序与中序遍历序列构造二叉树

import java.util.*;

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

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

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length != inorder.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(preorder, 0, 0, inorder.length - 1, index);
    }

    private TreeNode build(int[] preorder, int preStart, int inLeft,
                           int inRight, Map<Integer, Integer> index) {
        // 中序区间为空时，对应子树为空；preStart 无需继续读取。
        if (inLeft > inRight) return null;
        // 前序区间首元素是当前根，中序位置决定左子树节点数。
        int rootValue = preorder[preStart];
        int pivot = index.get(rootValue);
        int leftSize = pivot - inLeft;
        TreeNode root = new TreeNode(rootValue);
        root.left = build(preorder, preStart + 1, inLeft, pivot - 1, index);
        // 右子树前序起点需跳过根与完整左子树。
        root.right = build(preorder, preStart + leftSize + 1,
                pivot + 1, inRight, index);
        return root;
    }
}