給定二元樹的中序遍歷和後序遍歷陣列，建構並回傳該二元樹。假設沒有重複值。
Example:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]
Intuition
TIP
後序的最後一個元素是根；在中序中找到根的位置，左邊是左子樹、右邊是右子樹。
- 後序遍歷：左 -> 右 -> 根，所以最後一個元素永遠是根
- 中序遍歷：左 -> 根 -> 右，根的位置把陣列分成左右子樹
- 從後序尾端往前取根，先建右子樹再建左子樹（因為後序中右子樹在左子樹後面）
Approaches
1. Recursion + Linear Search — O(n^2) / O(n)
- Idea: 每次從後序尾端取根，在中序中線性搜尋根的位置來分割左右子樹
- Time:
O(n^2) - Space:
O(n)
class Solution {
private var postIdx = 0
fun buildTree(inorder: IntArray, postorder: IntArray): TreeNode? {
postIdx = postorder.size - 1
return build(inorder, postorder, 0, inorder.size - 1)
}
private fun build(inorder: IntArray, postorder: IntArray, inLeft: Int, inRight: Int): TreeNode? {
if (inLeft > inRight) return null
val rootVal = postorder[postIdx--]
val root = TreeNode(rootVal)
var inIdx = inLeft
while (inorder[inIdx] != rootVal) inIdx++
root.right = build(inorder, postorder, inIdx + 1, inRight)
root.left = build(inorder, postorder, inLeft, inIdx - 1)
return root
}
}⭐ 2. Recursion + HashMap — O(n) / O(n)
- Idea: 預先建立中序值到索引的映射，將搜尋根位置從 O(n) 降到 O(1)
- Time:
O(n) - Space:
O(n)
class Solution {
private var postIdx = 0
private lateinit var inorderMap: HashMap<Int, Int>
fun buildTree(inorder: IntArray, postorder: IntArray): TreeNode? {
postIdx = postorder.size - 1
inorderMap = HashMap()
for (i in inorder.indices) {
inorderMap[inorder[i]] = i
}
return build(postorder, 0, inorder.size - 1)
}
private fun build(postorder: IntArray, inLeft: Int, inRight: Int): TreeNode? {
if (inLeft > inRight) return null
val rootVal = postorder[postIdx--]
val root = TreeNode(rootVal)
val inIdx = inorderMap[rootVal]!!
root.right = build(postorder, inIdx + 1, inRight)
root.left = build(postorder, inLeft, inIdx - 1)
return root
}
}Why build the right subtree before the left?
因為後序遍歷的順序是「左 -> 右 -> 根」。postIdx 是全域遞減的指標，從根往前一個元素必定屬於右子樹。如果先建左子樹會打亂順序。這與 105 題（前序 + 中序）恰好相反。
🔑 Takeaways
- Pattern: 與 105 題互為鏡像，後序從尾端取根，先建右再建左
- Key trick: 理解前序/後序遍歷指標的遞進方向與子樹建構順序的對應關係