105. 从前序与中序遍历序列构造二叉树 (Medium)
专题归类： 05-二叉树 LeetCode 链接： https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定两个整数数组 preorder 和 inorder，其中 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 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorder中preorder保证为二叉树的前序遍历序列inorder保证为二叉树的中序遍历序列
题目详细分析
- 数据范围含义： 最多 3000 个节点，值覆盖 [-3000, 3000]，无重复值。无重复值意味着可以用哈希表将中序值映射到索引。
- 输入输出特征： 输入前序和中序两个数组，输出树的根节点。两个数组长度相等，且都是有效的遍历序列。
- 边界条件： 单节点时直接返回该节点；空区间返回 None。
- 核心约束： 必须用两种遍历结果唯一确定一棵二叉树。前序确定根节点，中序确定左右子树范围。
- 隐藏条件： 二叉树中无重复值，这是能用哈希表映射的前提。如果有重复值，就无法用值唯一确定位置，题目会更复杂。
小白版直白理解
就像你拿到了一个家族的两份家谱记录——第一份是按「先长辈后晚辈」的顺序记录所有人（前序：根→左→右），第二份是按「左半边家族→长辈→右半边家族」的顺序记录（中序：左→根→右）。你需要还原出完整的家族树。方法：从第一份记录中找出族长（第一个就是根），然后在第二份记录中找到族长在列表中的位置，左边就是左半边家族，右边就是右半边家族。对左右半边重复这个步骤。
解题思路
思路一：递归 + 哈希表（推荐）
核心思想：
- 前序的第一个元素是根节点。
- 在中序中找到根节点的位置，左边是左子树的中序，右边是右子树的中序。
- 根据左子树的节点数，可以从前序中划分出左子树的前序和右子树的前序。
- 递归构建左右子树。
关键： 用哈希表（字典）存储中序数组中每个值的索引，这样查找根节点在中序中的位置就是 O(1)。
def buildTree(preorder, inorder):
# 哈希表：值 → 在中序数组中的索引
index_map = {val: i for i, val in enumerate(inorder)}
def build(pre_l, pre_r, in_l, in_r):
"""构建子树
Args:
pre_l, pre_r: 前序数组的左右边界（闭区间）
in_l, in_r: 中序数组的左右边界（闭区间）
"""
if pre_l > pre_r:
return None
# 前序的第一个元素是根节点
root_val = preorder[pre_l]
root = TreeNode(root_val)
# 在中序中找到根节点的位置
in_idx = index_map[root_val]
# 左子树的节点数
left_size = in_idx - in_l
# 递归构建左右子树
# 前序中：根后 left_size 个是左子树前序，剩下的是右子树前序
root.left = build(pre_l + 1, pre_l + left_size, in_l, in_idx - 1)
root.right = build(pre_l + left_size + 1, pre_r, in_idx + 1, in_r)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)思路二：递归 + 指针扫描（不建哈希表）
用一个指针 pre_idx 扫描前序数组（全局变量），在中序数组中定位当前根节点，利用中序的左右范围分割左右子树。
def buildTree(preorder, inorder):
pre_idx = 0 # 前序数组的指针
def build(in_l, in_r):
nonlocal pre_idx
if in_l > in_r:
return None
# 取前序当前指针的值作为根节点
root_val = preorder[pre_idx]
root = TreeNode(root_val)
pre_idx += 1
# 在中序中找到根节点位置
in_idx = inorder.index(root_val) # O(n) 查找，可以优化为哈希表
# 注意：必须先构建左子树！
# 因为前序的顺序是「根→左→右」，指针前移意味着先找到左子树的根
root.left = build(in_l, in_idx - 1)
root.right = build(in_idx + 1, in_r)
return root
return build(0, len(inorder) - 1)注意：这种方式如果不配合哈希表，每次 inorder.index() 是 O(n)，总时间复杂度为 O(n
易错点
- 左子树大小的计算：
left_size = in_idx - in_l（中序中根的位置减左边界），然后用 left_size 来分割前序数组。 - 前序数组边界： 左子树前序区间是
[pre_l + 1, pre_l + left_size]，右子树前序区间是[pre_l + left_size + 1, pre_r]。注意 +1 和 -1 的边界细节。 - 递归的终止条件： 当区间左边界 > 右边界时返回 None，表示没有子节点。不是
>=，因为==时还有一个节点需要构建。 - 无重复值是前提： 如果有重复值，哈希表映射会有歧义。题目保证无重复。
- 先构建左子树再构建右子树： 前序的顺序是「根→左→右」，所以递归构建时也必须先左后右，这样才能和 pre_idx 指针的移动保持一致。
框架提炼
从前序+中序构建二叉树的标准模板：
def buildTree(preorder, inorder):
index_map = {val: i for i, val in enumerate(inorder)}
def build(pre_l, pre_r, in_l, in_r):
if pre_l > pre_r:
return None
root = TreeNode(preorder[pre_l])
in_idx = index_map[root.val]
left_size = in_idx - in_l
root.left = build(pre_l + 1, pre_l + left_size, in_l, in_idx - 1)
root.right = build(pre_l + left_size + 1, pre_r, in_idx + 1, in_r)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)推广到其他遍历组合：
- 中序 + 后序： 后序的最后一个元素是根，同样在中序中找到根的位置分割。
- 前序 + 后序： 不能唯一确定二叉树（除非是满二叉树/真二叉树）。
关键公式： left_size = in_idx - in_l 这一步是核心，连接了前序和中序两个数组。
关联题目
- 106-从中序与后序遍历序列构造二叉树 — 完全对称的思路：后序末尾是根，中序找根位置分割。
- 108-将有序数组转换为二叉搜索树 — 更简单的构造题，只需一个有序数组即可构建 BST。
- 889-从前序和后序遍历构造二叉树 — 前序+后序可以构造但不唯一，需要额外条件（如真二叉树）。