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

题目链接（中等）

题目描述

给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的前序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

数据范围：

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证为二叉树的前序遍历序列
• inorder 保证为二叉树的中序遍历序列

示例

示例 1：

输入： preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出： [3,9,20,null,null,15,7]

示例 2：

输入： preorder = [-1], inorder = [-1]
输出： [-1]

核心思路

前序遍历的形式：

[ 根节点, [左子树的前序遍历], [右子树的前序遍历] ]

中序遍历的形式：

[ [左子树的中序遍历], 根节点, [右子树的中序遍历] ]

关键观察：

1. 前序的第一个元素就是当前子树的根；
2. 在中序里找到这个根，左边是左子树，右边是右子树；
3. 由中序中根左边的元素个数，可以推出前序中左、右子树各占多少；
4. 递归构造左、右子树，接到根上。

下面从易到难给出四种写法，逻辑完全相同，只是参数传递方式不同。

---

方法一：切片 + 线性查找（最直观）

思路及解法

直接把「左子树前序」「右子树前序」「左子树中序」「右子树中序」四段列表用切片切出来，递归传递。

• 根 = preorder[0]；
• 根在中序中的位置 idx = inorder.index(preorder[0])；
• 左子树：前序 preorder[1:1+idx]，中序 inorder[:idx]；
• 右子树：前序 preorder[1+idx:]，中序 inorder[idx+1:]。

优点：逻辑一眼看穿，代码最短。
缺点：inorder.index() 是 $O(n)$，切片会复制列表，整体时间 $O(n^2)$、空间 $O(n \log n)$。

代码

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        if not inorder:
            return None
        root = TreeNode(preorder[0])
        idx = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:1 + idx], inorder[:idx])
        root.right = self.buildTree(preorder[1 + idx:], inorder[idx + 1:])
        return root

复杂度分析

• 时间复杂度：$O(n^2)$，每次 index 查找是 $O(n)$，共 $n$ 次。
• 空间复杂度：$O(n \log n)$ ~ $O(n^2)$，切片复制列表的额外开销。

---

方法二：切片 + 队列（共享前序）

思路及解法

观察到一个事实：前序序列的顺序天然就是「建树的顺序」——先根，再左子树的全部节点，再右子树的全部节点。递归建树时的处理顺序也完全一致。

因此可以把 preorder 转成队列，所有递归共享同一个队列，每层从队首弹出一个元素作为当前子树的根。因为递归先深入左子树，左子树会把队列中属于它的节点全部弹完，剩下的自然就是右子树的节点。

• preorder.popleft() 取出根；
• inorder.index(...) 定位根，切分中序；
• 递归建左、右子树。

队列的 FIFO 特性正好匹配前序的顺序，避免了手动维护前序下标。

优点：不需要显式传递前序区间，代码更简洁。
缺点：index 和切片仍是 $O(n)$，整体时间 $O(n^2)$。

代码

from collections import deque

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        preorder = deque(preorder)

        def build(preorder, inorder):
            if inorder:
                idx = inorder.index(preorder.popleft())
                root = TreeNode(inorder[idx])
                root.left = build(preorder, inorder[:idx])
                root.right = build(preorder, inorder[idx + 1:])
                return root

        return build(preorder, inorder)

复杂度分析

• 时间复杂度：$O(n^2)$，同方法一。
• 空间复杂度：$O(n \log n)$ ~ $O(n^2)$。

---

方法三：哈希表 + 四参数区间

思路及解法

用哈希表消除 index 的线性查找，把查找降到 $O(1)$；再用下标区间代替切片，避免复制列表。

四个参数 build(pre_l, pre_r, in_l, in_r) 分别表示当前子树在前序和中序中的区间（闭区间）。

• 根 = preorder[pre_l]，pre_r 是区间右边界；
• 根在中序中的位置 idx = index[root_val]；
• 左子树节点数 size = idx - in_l；
• 左子树：build(pre_l + 1, pre_l + size, in_l, idx - 1)；
• 右子树：build(pre_l + size + 1, pre_r, idx + 1, in_r)。

优点：时间 $O(n)$、空间 $O(n)$。
缺点：四个参数长得像，容易看晕；pre_l + size + 1 这种式子需要想一下。

代码

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        n = len(preorder)
        index = {val: i for i, val in enumerate(inorder)}

        def build(pre_l: int, pre_r: int, in_l: int, in_r: int) -> TreeNode | None:
            if pre_l > pre_r:
                return None
            root_val = preorder[pre_l]
            root = TreeNode(root_val)

            idx = index[root_val]          # 根在中序中的位置
            size = idx - in_l              # 左子树节点数

            root.left = build(pre_l + 1, pre_l + size, in_l, idx - 1)
            root.right = build(pre_l + size + 1, pre_r, idx + 1, in_r)
            return root

        return build(0, n - 1, 0, n - 1)

复杂度分析

• 时间复杂度：$O(n)$，每个节点创建一次，哈希表使根定位 $O(1)$。
• 空间复杂度：$O(n)$，哈希表 $O(n)$，递归栈深度最坏 $O(n)$。

---

方法四：哈希表 + 起点 + 长度（推荐）

思路及解法

方法三需要同时维护前序的两个边界 pre_l、pre_r 和中序的两个边界 in_l、in_r，一共四个参数，容易看晕。

简化思路：把「区间」改成「起点 + 长度」。只需要三个参数：

• pre_start：当前子树在 preorder 中的起点；
• in_start：当前子树在 inorder 中的起点；
• length：当前子树的节点个数。

由这三个参数和根在中序中的位置 root_idx，可以推出：

• 左子树长度 left_size = root_idx - in_start；
• 右子树长度 right_size = length - 1 - left_size；
• 左子树起点：前序 pre_start + 1，中序 in_start；
• 右子树起点：前序 pre_start + 1 + left_size，中序 root_idx + 1。

优点：

• 时间 $O(n)$、空间 $O(n)$；
• 参数只有三个，命名直观（pre_start、in_start、length）；
• 不需要维护右边界，少一个变量少一个出错点。

代码

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        index = {val: i for i, val in enumerate(inorder)}

        def build(pre_start: int, in_start: int, length: int) -> TreeNode | None:
            """用 preorder[pre_start:pre_start+length] 和
               inorder[in_start:in_start+length] 构造子树"""
            if length == 0:
                return None

            root_val = preorder[pre_start]
            root = TreeNode(root_val)

            root_idx = index[root_val]                # 根在中序中的位置
            left_size = root_idx - in_start           # 左子树长度
            right_size = length - 1 - left_size       # 右子树长度

            root.left = build(pre_start + 1, in_start, left_size)
            root.right = build(pre_start + 1 + left_size, root_idx + 1, right_size)
            return root

        return build(0, 0, len(preorder))

复杂度分析

• 时间复杂度：$O(n)$，每个节点创建一次，哈希表使根定位 $O(1)$。
• 空间复杂度：$O(n)$，哈希表 $O(n)$，递归栈深度最坏 $O(n)$。