給定二元樹的前序遍歷和中序遍歷陣列，建構並回傳該二元樹。假設沒有重複值。
Example:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
Intuition
TIP
前序的第一個元素是根；在中序中找到根的位置，左邊是左子樹、右邊是右子樹。
- 前序遍歷：根 -> 左 -> 右，所以第一個元素永遠是根
- 中序遍歷：左 -> 根 -> 右，根的位置把陣列分成左右子樹
- 用 HashMap 預存中序的 index，避免每次線性搜尋
Approaches
1. Recursion + Linear Search — O(n^2) / O(n)
- Idea: 每次遞迴從前序取根，在中序中線性搜尋根的位置來分割左右子樹
- Time:
O(n^2)，每次搜尋根的位置需要 O(n) - Space:
O(n)
class Solution {
private var preIdx = 0
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
preIdx = 0
return build(preorder, inorder, 0, inorder.size - 1)
}
private fun build(preorder: IntArray, inorder: IntArray, inLeft: Int, inRight: Int): TreeNode? {
if (inLeft > inRight) return null
val rootVal = preorder[preIdx++]
val root = TreeNode(rootVal)
var inIdx = inLeft
while (inorder[inIdx] != rootVal) inIdx++
root.left = build(preorder, inorder, inLeft, inIdx - 1)
root.right = build(preorder, inorder, inIdx + 1, inRight)
return root
}
}⭐ 2. Recursion + HashMap — O(n) / O(n)
- Idea: 預先建立中序值到索引的映射，將搜尋根位置的時間從 O(n) 降到 O(1)
- Time:
O(n) - Space:
O(n)
class Solution {
private var preIdx = 0
private lateinit var inorderMap: HashMap<Int, Int>
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
preIdx = 0
inorderMap = HashMap()
for (i in inorder.indices) {
inorderMap[inorder[i]] = i
}
return build(preorder, 0, inorder.size - 1)
}
private fun build(preorder: IntArray, inLeft: Int, inRight: Int): TreeNode? {
if (inLeft > inRight) return null
val rootVal = preorder[preIdx++]
val root = TreeNode(rootVal)
val inIdx = inorderMap[rootVal]!!
root.left = build(preorder, inLeft, inIdx - 1)
root.right = build(preorder, inIdx + 1, inRight)
return root
}
}Why build the left subtree before the right?
因為前序遍歷的順序是「根 -> 左 -> 右」。preIdx 是全域遞增的指標，建完根之後下一個元素必定屬於左子樹。如果先建右子樹會打亂順序。
🔑 Takeaways
- Pattern: 利用兩種遍歷序列的互補資訊重建樹
- Key trick: 用 HashMap 將「在陣列中查找位置」從 O(n) 優化到 O(1)，是常見的空間換時間策略