🌱 二叉树构造题精讲：前序 + 中序建树 & 有序数组构造 BST
本文围绕二叉树的两类构造类题目展开解析：
- 从前序与中序遍历序列构造二叉树
- 将有序数组转换为二叉搜索树
我们将从「已知遍历构造树」和「平衡构造 BST」两个角度，拆解树结构的构建逻辑，彻底吃透构造题型。
📌 题目一：105. 从前序与中序遍历序列构造二叉树
📝 题目描述
给定两棵树的遍历序列：
preorder（前序遍历）：根 -> 左 -> 右inorder（中序遍历）：左 -> 根 -> 右
请根据这两种遍历构造原始二叉树。
🔍 解题思路
核心思路：
- 前序遍历的第一个元素一定是根节点；
- 在中序遍历中找到这个根节点的位置，可以确定左右子树的元素范围；
- 递归构造左右子树。
✅ 解法：递归构造
func buildTree(preorder []int, inorder []int) *TreeNode {
inMap := map[int]int{
}
for i, val := range inorder {
inMap[val] = i
}
var build func(pl, pr, il, ir int) *TreeNode
build = func(pl, pr, il, ir int) *TreeNode {
if pl > pr || il > ir {
return nil
}
rootVal := preorder[pl]
root := &TreeNode{
Val: rootVal}
idx := inMap[rootVal]
leftSize := idx - il
root.Left = build(pl+1, pl+leftSize, il, idx-1)
root.Right = build(pl+leftSize+1, pr, idx+1, ir)
return root
}
return build(0, len(preorder)-1, 0, len(inorder)-1)
}
📘 思路详解
- 使用
inMap来快速定位中序中某个值的位置，避免每次线性搜索； - 用索引控制遍历范围，不要切片传参，会影响性能；
- 每次递归缩小当前处理的 preorder 和 inorder 区间。
⚠️ 注意事项：
preorder[pl]是当前子树的根节点；- 左子树的大小为
idx - il； - 左右子树递归时注意索引边界不要写错。
📌 题目二：108. 将有序数组转换为二叉搜索树
📝 题目描述
给你一个升序排序的整数数组，请你将其转化为一棵高度平衡的二叉搜索树（BST）。
🔍 解题思路
关键点：
- 数组有序 → 可用中间元素构建根节点；
- 左边递归为左子树，右边递归为右子树；
- 中间元素选择策略：可以取中间偏左或偏右均可。
✅ 解法：递归 + 中点分割
func sortedArrayToBST(nums []int) *TreeNode {
var build func(left, right int) *TreeNode
build = func(left, right int) *TreeNode {
if left > right {
return nil
}
mid := (left + right) / 2
root := &TreeNode{
Val: nums[mid]}
root.Left = build(left, mid-1)
root.Right = build(mid+1, right)
return root
}
return build(0, len(nums)-1)
}
💭 思维补充
- 二叉搜索树要求：左 < 根 < 右；
- 高度平衡树要求：每个节点左右子树高度差不超过 1；
- 因此「中间作为根」是构造平衡 BST 的最优策略。
🧠 总结 & 对比
| 题目 | 类型 | 输入 | 输出 | 核心操作 |
|---|---|---|---|---|
| 105 | 构造普通二叉树 | 前序 + 中序遍历 | 树结构 | 递归 + 分治（索引控制） |
| 108 | 构造平衡 BST | 有序数组 | BST 树结构 | 递归 + 二分中点 |
🎯 通用构造套路小结：
- 明确根节点从何而来（前序 or 中点）；
- 找到左右子树的边界；
- 用索引控制子问题的范围；
- 构建节点，递归处理左右子树；
- 特别注意边界条件与 base case。
✨ 进阶思考
- 如果输入是 中序 + 后序，你还能反推出树吗？
- 如果输入是 BST + 任意遍历，你能判断树结构吗？
这些问题都是构造类题目的常见变体，建议从这两题出发逐步拓展思维路径。
下一篇将带你探索搜索树相关的问题，从验证 BST 到查找第 K 小元素，一起掌握搜索树的价值！
如有帮助，欢迎点赞收藏，更多结构题内容持续更新中 🧠💡
