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

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 从前序与中序的完整区间开始递归构建
        return build(preorder, 0, preorder.length-1, 
                    inorder, 0, inorder.length-1);
    }

    private TreeNode build(int[] pre, int preStart, int preEnd,
                          int[] in, int inStart, int inEnd) {
        // 递归终止条件：前序区间为空时，没有节点可构建
        if (preStart > preEnd) return null;

        // 前序区间第一个元素一定是当前子树根节点值
        int rootVal = pre[preStart];
        // rootIndex 记录根节点在中序数组中的位置
        int rootIndex = -1;
        // 在线性区间中查找根节点位置（O(n)）
        for (int i = inStart; i <= inEnd; i++) {
            if (in[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        // 左子树节点个数 = 中序中“根左侧元素个数”
        int leftSize = rootIndex - inStart;

        // 创建当前根节点
        TreeNode root = new TreeNode(rootVal);
        // 递归构建左子树：
        // 前序区间：[preStart+1, preStart+leftSize]
        // 中序区间：[inStart, rootIndex-1]
        root.left = build(pre, preStart+1, preStart+leftSize,
                         in, inStart, rootIndex-1);
        // 递归构建右子树：
        // 前序区间：[preStart+leftSize+1, preEnd]
        // 中序区间：[rootIndex+1, inEnd]
        root.right = build(pre, preStart+leftSize+1, preEnd,
                           in, rootIndex+1, inEnd);
        // 返回当前构建完成的子树根节点
        return root;
    }
}

class Solution {
    // 哈希表：中序值 -> 对应索引，用于 O(1) 定位根节点分割点
    private Map<Integer, Integer> inMap = new HashMap<>();
    // preIndex 指向当前应作为“根”的前序元素位置
    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 预处理中序数组，建立值到索引的映射
        for (int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
        // 从中序完整区间 [0, n-1] 开始构建
        return build(preorder, 0, inorder.length-1);
    }

    private TreeNode build(int[] pre, int left, int right) {
        // 递归终止条件：区间为空，返回 null
        if (left > right) return null;

        // 取前序当前元素作为根节点值，并将指针后移
        int rootVal = pre[preIndex++];
        // 创建根节点
        TreeNode root = new TreeNode(rootVal);

        // O(1) 查到根节点在中序中的位置，作为左右子树分割点
        int rootIndex = inMap.get(rootVal);

        // 先构建左子树（中序 left 到 rootIndex-1）
        root.left = build(pre, left, rootIndex-1);
        // 再构建右子树（中序 rootIndex+1 到 right）
        root.right = build(pre, rootIndex+1, right);
        // 返回当前子树根节点
        return root;
    }
}