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

核心思路

· 前序遍历：[根节点, [左子树前序], [右子树前序]]
· 中序遍历：[[左子树中序], 根节点, [右子树中序]]

因此：

1. 前序的第一个元素就是根节点
2. 在中序中找到根节点的位置，左边是左子树，右边是右子树
3. 用 HashMap 预处理中序的值→下标映射，避免每次线性查找
4. 递归构建左右子树

方法一：递归 + HashMap（推荐）

class Solution {
    private Map<Integer, Integer> indexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 预处理：记录中序遍历中每个值对应的下标
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(preorder, 0, n - 1, inorder, 0, n - 1);
    }

    private TreeNode build(int[] preorder, int preLeft, int preRight,
                           int[] inorder,  int inLeft,  int inRight) {
        if (preLeft > preRight) return null;

        // 前序第一个元素是根
        int rootVal = preorder[preLeft];
        TreeNode root = new TreeNode(rootVal);

        // 根在中序中的位置
        int inRoot = indexMap.get(rootVal);
        // 左子树节点个数
        int leftSize = inRoot - inLeft;

        // 递归构建左、右子树
        root.left = build(preorder, preLeft + 1, preLeft + leftSize,
                          inorder,  inLeft,     inRoot - 1);
        root.right = build(preorder, preLeft + leftSize + 1, preRight,
                           inorder,  inRoot + 1,             inRight);

        return root;
    }
}

关键下标推导

设当前子树：

· 前序区间 [preLeft, preRight]
· 中序区间 [inLeft, inRight]
· 根在中序中的位置 inRoot
· 左子树节点数 leftSize = inRoot - inLeft

子树 前序区间 中序区间
左子树 [preLeft + 1, preLeft + leftSize] [inLeft, inRoot - 1]
右子树 [preLeft + leftSize + 1, preRight] [inRoot + 1, inRight]

方法二：迭代法（进阶）

利用前序遍历模拟 DFS，用栈记录路径，借助中序判断当前节点是否还有左子树。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) return null;

        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);

        int inIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preVal = preorder[i];
            TreeNode node = stack.peek();

            // 若栈顶不等于中序当前值，说明还有左子树
            if (node.val != inorder[inIndex]) {
                node.left = new TreeNode(preVal);
                stack.push(node.left);
            } else {
                // 回溯到正确的父节点
                while (!stack.isEmpty() && stack.peek().val == inorder[inIndex]) {
                    node = stack.pop();
                    inIndex++;
                }
                node.right = new TreeNode(preVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}

复杂度分析

方法 时间复杂度 空间复杂度
递归 + HashMap O(n) O(n)（哈希表 + 递归栈）
迭代法 O(n) O(h)，h 为树高

若不用 HashMap 而在中序中线性查找根，时间会退化为 O(n²)（如链状树）。

示例验证

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

根 = 3
中序中 3 的下标 = 1 → 左子树 [9]，右子树 [15, 20, 7]
左：pre[9] in[9] → 叶子 9
右：pre[20,15,7] in[15,20,7] → 根 20，左 15，右 7

结果：
      3
     / \
    9  20
      /  \
     15   7

两个方法输出一致 ✅