MediumRating 1541
1382. Balance a Binary Search Tree
divide-and-conquergreedytreedepth-first-searchbinary-search-treebinary-tree
解題說明
Balance a Binary Search Tree
題目描述： 給定一棵二元搜尋樹的根節點 root，回傳一棵平衡的二元搜尋樹，包含相同的節點值。如果有多個答案，回傳任意一個即可。
解題思路： 分兩步驟：(1) 對 BST 進行中序遍歷，得到一個排序陣列；(2) 從排序陣列遞迴地建構平衡 BST。建構時每次選取陣列中間元素作為根節點，左半部分遞迴建構左子樹，右半部分建構右子樹。這樣保證樹的高度為 O(log n)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 中序遍歷 O(n) + 建構平衡 BST O(n)
空間複雜度：O(n) — 儲存排序陣列 O(n) + 遞迴堆疊 O(log n)
虛擬碼
1. Perform inorder traversal on the BST to get a sorted array 2. Build balanced BST from sorted array: a. If left > right, return null b. mid = (left + right) / 2 c. Create node with sorted[mid] d. node.left = build(sorted, left, mid-1) e. node.right = build(sorted, mid+1, right) f. Return node 3. Return the root of newly built tree
其他解法
方法二：Day-Stout-Warren (DSW) 演算法 先將 BST 轉換為右向鏈表（vine），再透過左旋轉操作將其轉換為平衡 BST。時間 O(n)，空間 O(1)（原地操作，不需要額外陣列），但實現較為複雜。
方法三：AVL / 紅黑樹插入 將原始 BST 的節點逐一插入到 AVL 或紅黑樹中，自動保持平衡。時間複雜度 O(n log n)，不如前兩種方法高效。
延伸思考
- DSW 演算法如何做到 O(1) 額外空間？它的核心旋轉操作是什麼？
- 如果需要在不重建整棵樹的情況下平衡 BST（例如只允許旋轉操作），你會使用什麼策略？
- 如果 BST 的節點數非常大（超過記憶體容量），如何實現外部排序 + 建構？