从前序与中序遍历序列构造二叉树
Construct Binary Tree from Preorder and Inorder Traversal
本机进度仅保存在当前浏览器
题目描述
给定两个整数数组 preorder 和 inorder，其中 preorder 是二叉树的前序遍历，inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点（假设无重复值）。
示例：preorder = [3, 9, 20, 15, 7]，inorder = [9, 3, 15, 20, 7]，构造出 [3, 9, 20, null, null, 15, 7]。
解题思路
- 前序的第一个元素是根；在中序里找到它，左侧是左子树、右侧是右子树，由此确定两段子数组规模。
- 递归构造：按左右子树的规模切分前序与中序数组，分别建树后接到根上。
- 为避免每次线性查找根的位置，用哈希表预存「值 -> 中序下标」；传区间下标代替切片，避免复制数组。
- 无重复值是哈希定位成立的前提；重复值时该问题无唯一解。
参考实现
查看参考实现Python · 建议先自行作答
def buildTree(preorder, inorder):
# 值 -> 中序下标，O(1) 定位根
idx = {v: i for i, v in enumerate(inorder)}
def build(pre_l, pre_r, in_l, in_r):
if pre_l > pre_r:
return None
root_val = preorder[pre_l]
root = TreeNode(root_val)
mid = idx[root_val]
left_size = mid - in_l
root.left = build(pre_l + 1, pre_l + left_size, in_l, mid - 1)
root.right = build(pre_l + left_size + 1, pre_r, mid + 1, in_r)
return root
return build(0, len(preorder) - 1, 0, len(inorder) - 1)