1382. Balance a Binary Search Tree

📘 題目敘述

給你一棵二元搜尋樹（Binary Search Tree, BST）的根節點 root，請回傳一棵高度平衡（balanced）的二元搜尋樹，且它包含完全相同的節點值。

如果有多種答案，回傳任意一種都可以。

一棵 BST 被稱為平衡的，如果每個節點的左右子樹深度差的絕對值都不超過 1。

條件限制

節點數量在範圍 [1, 10^4]
1 <= Node.val <= 10^5

🧠 解題思路

我先想清楚這題想要的是什麼：

我不需要保留原本樹的形狀，只需要保留「所有值」，並重新組成一棵平衡 BST。

所以我把問題拆成兩段：

把樹的所有節點值收集出來
我用 DFS 走訪整棵樹，把每個節點的 val 放進 nums。
用這些值重新建一棵平衡 BST
平衡 BST 最直覺的做法就是：把值排序後變成一個遞增陣列，接著每次選中間當根，左右兩邊遞迴建樹。這樣每層切一半，高度就會接近平衡。

這份 code 的邏輯就是：search(root) 收集所有值 → sort(nums) 變成遞增序列 → build(l, r) 用中點建立平衡樹。

所有變數

nums：存整棵樹所有節點值的陣列（收集完後會排序）
l：build(l, r) 的左邊界
r：build(l, r) 的右邊界
m：目前區間 [l, r] 的中點索引
root（build 裡的區域變數）：新建立的子樹根節點指標

🪜 主要流程步驟

1. 先用 DFS 把所有節點值收集到 `nums`

我寫了一個 search(root)：只要 root 不為空，就把 root->val 放進 nums，然後遞迴走左子樹、右子樹。這步的目的很單純：先把「有哪些值」全部拿到。

2. 把 `nums` 排序，得到遞增序列

因為要重建 BST，排序後的陣列會變成 BST 的中序結果（遞增）。有了遞增陣列，我就可以用「選中間當根」的方法保證平衡。

3. 用 `build(l, r)` 從排序後的陣列建平衡 BST

build(l, r) 代表：用 nums[l...r] 這段數值來建一棵平衡 BST。

如果 l > r，代表這段沒有元素，回傳 nullptr
否則取中點 m = (l + r) / 2
- 建立根節點 new TreeNode(nums[m])
- 左子樹用 build(l, m - 1) 建
- 右子樹用 build(m + 1, r) 建

這樣每一層都把資料切成左右兩半，所以整棵樹的高度會被壓到接近平衡。

4. 回傳新樹根

在 balanceBST(root) 裡，收集 + 排序後，直接回傳 build(0, nums.size() - 1) 的結果，這就是平衡後的 BST。

💻 程式碼實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    vector<int> nums;
    void search(TreeNode* root) {
        if (root) {
            nums.push_back(root->val);
            search(root->left);
            search(root->right);
        }
        return;
    }
    TreeNode* build(int l, int r) {
        if (l > r) {
            return nullptr;
        }
        int m = (l + r) / 2;
        TreeNode* root = new TreeNode(nums[m]);
        root->left = build(l, m - 1);
        root->right = build(m + 1, r);
        return root;
    }
    TreeNode* balanceBST(TreeNode* root) {
        search(root);
        sort(nums.begin(), nums.end());
        return build(0, nums.size() - 1);
    }
};

🔗 題目連結

https://leetcode.com/problems/balance-a-binary-search-tree/