給定一個升序排列的整數陣列，將其轉換為一棵高度平衡的二元搜尋樹 (BST)。高度平衡意指每個節點的左右子樹高度差不超過 1。
Example:
Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] (其中一個合法答案)
Intuition
TIP
取陣列中間元素作為根，左半部建左子樹，右半部建右子樹，遞迴進行即可保證平衡。
- 排序陣列的中間元素作為根，可以確保左右子樹的節點數量盡量相等
- 這是一個經典的分治法應用
Approaches
1. Iterative + Queue (carry range) — O(n) / O(n)
- Idea: 用佇列存「節點 + 它負責的區間」，每次取中點建子節點，模擬遞迴
- Time:
O(n)- 每個元素建一個節點 - Space:
O(n)- 佇列
class Solution {
fun sortedArrayToBST(nums: IntArray): TreeNode? {
if (nums.isEmpty()) return null
val mid = (nums.size - 1) / 2
val root = TreeNode(nums[mid])
val queue = ArrayDeque<Triple<TreeNode, Int, Int>>()
queue.addLast(Triple(root, 0, nums.size - 1))
while (queue.isNotEmpty()) {
val (node, lo, hi) = queue.removeFirst()
val m = lo + (hi - lo) / 2
if (lo <= m - 1) {
val lm = lo + (m - 1 - lo) / 2
node.left = TreeNode(nums[lm]).also { queue.addLast(Triple(it, lo, m - 1)) }
}
if (m + 1 <= hi) {
val rm = (m + 1) + (hi - m - 1) / 2
node.right = TreeNode(nums[rm]).also { queue.addLast(Triple(it, m + 1, hi)) }
}
}
return root
}
}⭐ 2. Recursive Divide & Conquer — O(n) / O(log n)
- Idea: 每次取中間元素作為根節點，左半段遞迴建左子樹，右半段遞迴建右子樹
- Time:
O(n)，每個元素處理一次 - Space:
O(log n)，遞迴深度為平衡樹高度
class Solution {
fun sortedArrayToBST(nums: IntArray): TreeNode? {
return build(nums, 0, nums.size - 1)
}
private fun build(nums: IntArray, left: Int, right: Int): TreeNode? {
if (left > right) return null
val mid = left + (right - left) / 2
val node = TreeNode(nums[mid])
node.left = build(nums, left, mid - 1)
node.right = build(nums, mid + 1, right)
return node
}
}🔑 Takeaways
- Pattern: 分治法建樹 — 排序陣列取中間點作根，遞迴建左右子樹
- Key trick: 選擇中間元素作為根節點是保證平衡的關鍵，這個技巧也適用於建構平衡 BST 的其他場景