推理二叉树

/*
 * 思路：
 * 1. 前序遍历的第一个元素是根节点。
 * 2. 在中序遍历中找到根节点的位置，其左边是左子树，右边是右子树。
 * 3. 递归构建左子树和右子树。
 * 4. 使用 Java Stream API 简化代码。
 */

import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private Map<Integer, Integer> inorderIndexMap;
    private int preorderIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preorderIndex = 0;
        inorderIndexMap = IntStream.range(0, inorder.length).boxed().collect(Collectors.toMap(i -> inorder[i], i -> i));
        return helper(preorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int inorderStart, int inorderEnd) {
        if (inorderStart > inorderEnd) {
            return null;
        }

        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);
        int inorderIndex = inorderIndexMap.get(rootVal);

        root.left = helper(preorder, inorderStart, inorderIndex - 1);
        root.right = helper(preorder, inorderIndex + 1, inorderEnd);

        return root;
    }
}