🌱 二叉樹構造題精講：前序 + 中序建樹 & 有序數組構造 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) *TreeNodebuild = 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 - ilroot.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) *TreeNodebuild = func(left, right int) *TreeNode {if left > right {return nil}mid := (left + right) / 2root := &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 小元素，一起掌握搜索樹的價值！
如有幫助，歡迎點贊收藏，更多結構題內容持續更新中 🧠💡
