Description
給定一個升序排列的整數陣列，將其轉換為一棵高度平衡的二元搜尋樹 (BST)。高度平衡意指每個節點的左右子樹高度差不超過 1。
Example:
Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] (其中一個合法答案)
Intuition#
取陣列中間元素作為根，左半部建左子樹，右半部建右子樹，遞迴進行即可保證平衡。
- 排序陣列的中間元素作為根，可以確保左右子樹的節點數量盡量相等
- 這是一個經典的分治法應用
Approaches#
⭐ 1: 遞迴分治#
- 概念: 每次取中間元素作為根節點，左半段遞迴建左子樹，右半段遞迴建右子樹
- 時間複雜度:
O(n)，每個元素處理一次 - 空間複雜度:
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: 分治法建樹 — 排序陣列取中間點作根，遞迴建左右子樹
- 關鍵技巧: 選擇中間元素作為根節點是保證平衡的關鍵，這個技巧也適用於建構平衡 BST 的其他場景