题解：从前序和中序遍历构造二叉树
解题思路
题目给定了二叉树的前序遍历和中序遍历序列，我们需要从这两种遍历序列中恢复出原始的二叉树结构，并最终返回该树的层序遍历结果。
首先，回顾二叉树的前序遍历和中序遍历的特点：
- 前序遍历：先访问根节点，再递归访问左子树，最后访问右子树。其顺序为：根 -> 左子树 -> 右子树。
P4064.从前序与中序遍历序列构造二叉树
在线刷题
给定两个整数数组 preorder 和 inorder，其中 preorder 是这棵树的先序遍历，inorder 是同一棵树的中序遍历。请你把这棵二叉树构造出来，并返回根节点。
样例1
输入
5 5
3 9 20 15 7
9 3 15 20 7
输出
3 9 20 null null 15 7
样例2
输入
1 1
-1
-1
输出
-1
提示
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder 和 inorder 中都没有重复元素inorder 中每个值都在 preorder 中出现preorder 保证是某棵树的先序序列inorder 保证是同一棵树的中序序列
方法一：递归划分区间（DFS + 哈希表）
构造二叉树的条件是：确定根+确定左子树和右子树。
而:
- 先序遍历的第一个元素一定是当前子树的根
- 中序遍历里，根左边是左子树，根右边是右子树
如下图所示👇
所以我们可以写一个递归函数 dfs(preL, preR, inL, inR)，表示：
- 当前要构建的子树，先序范围是
[preL, preR]
- 中序范围是
[inL, inR]
每次递归：
- 取根:
rootVal = preorder[preL]
- 在中序
inorder里找到rootVal的下标 k
- 左子树大小
leftSize = k - inL
- 递归构建左子树：
- 先序：
[preL+1, preL+leftSize]
- 中序：
[inL, k-1]
- 递归构建右子树：
- 先序：
[preL+leftSize+1, preR]
- 中序：
[k+1, inR]
注意一点：如果每次都在中序数组里线性找 k，会退化成 O(n^2)。
所以我们先用哈希表 idx[val] = 在 inorder 中的位置，这样找根位置就是 O(1)。
代码实现
from collections import deque
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
n = len(preorder)
if n == 0:
return None
# inorder 值 -> 下标，O(1) 定位根节点
idx = {v: i for i, v in enumerate(inorder)}
def dfs(preL: int, preR: int, inL: int, inR: int) -> Optional[TreeNode]:
# 区间为空，没有节点
if preL > preR:
return None
# 先序区间第一个元素就是当前根
root_val = preorder[preL]
root = TreeNode(root_val)
# 根在中序中的位置
k = idx[root_val]
# 左子树节点个数
left_size = k - inL
# 构建左子树
root.left = dfs(
preL + 1,
preL + left_size,
inL,
k - 1,
)
# 构建右子树
root.right = dfs(
preL + left_size + 1,
preR,
k + 1,
inR,
)
return root
return dfs(0, n - 1, 0, n - 1)
def serialize_level_order(root: Optional[TreeNode]) -> str:
if root is None:
return ""
q = deque([root])
out = []
while q:
node = q.popleft()
if node is None:
out.append("null")
continue
out.append(str(node.val))
q.append(node.left)
q.append(node.right)
# 去掉末尾无意义的 null
while out and out[-1] == "null":
out.pop()
return " ".join(out)
def main():
# ACM 输入格式：
# 第一行: n m
# 第二行: preorder 的 n 个数
# 第三行: inorder 的 m 个数
n, m = map(int, input().split())
preorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))
root = Solution().buildTree(preorder, inorder)
print(serialize_level_order(root))
if __name__ == "__main__":
main()
复杂度分析
面试问答
1. 本题核心思路
递归。还原二叉树的先决条件是：确定根+确定左子树和右子树。考虑先序首元素是根，中序按根一刀切成左右子树，再递归构造左右区间。为了优化复杂度，不在中序里反复找根，用哈希表把“值 -> 下标”先预处理好。
