# 1382. Balance a Binary Search Tree

**練習日期：** 2026-02-09
**難度：** Medium
**類型：** Tree、Binary Search Tree、Divide and Conquer、Depth-First Search

## 📘 題目敘述

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

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

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

### 條件限制

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

## 🧠 解題思路

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

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

所以我把問題拆成兩段：

1. **把樹的所有節點值收集出來**
我用 DFS 走訪整棵樹，把每個節點的 `val` 放進 `nums`。

2. **用這些值重新建一棵平衡 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/description/