# 110. Balanced Binary Tree

**練習日期：** 2026-02-08
**難度：** Easy
**類型：** Tree、Depth-First Search、Binary Tree

## 📘 題目敘述

給你一棵二元樹 `root`，判斷它是否為高度平衡（height-balanced）的二元樹。

高度平衡的二元樹定義為：對於樹中的每一個節點，它的左右子樹高度差的絕對值不超過 `1`。

### 條件限制

* 樹中節點的數量在範圍 `[0, 5000]`
* `-10^4 <= Node.val <= 10^4`

## 🧠 解題思路

我在思考這題時，先抓住一個最核心的問題：

> **只要我知道某個節點左右子樹的高度，就能立刻判斷這個節點是否平衡。**

所以最直覺的方法就是用 DFS 遞迴去算高度，並且在算高度的同時順便檢查每個節點是否平衡。

為了避免重複計算，我讓 `check(x)` 這個函式同時做兩件事，而且用「回傳值」帶狀態：

* 如果 `x` 這棵子樹是平衡的，`check(x)` 回傳它的高度（>= 0）
* 如果 `x` 這棵子樹不平衡，`check(x)` 回傳 `-1`

這樣一來，只要某個地方已經不平衡，我就可以一路往上直接回傳 `-1`，不需要再算更多高度，等於提早結束。

### 所有變數

* `root`：題目輸入的樹根節點
* `x`：`check` 函式目前要檢查的節點
* `l`：左子樹的結果（平衡時是高度，不平衡時是 `-1`）
* `r`：右子樹的結果（平衡時是高度，不平衡時是 `-1`）

## 🪜 主要流程步驟

### 1. 設計 `check(x)` 的回傳規則（高度 / -1）

`check(x)` 不是單純回傳高度，而是：

* 平衡 → 回傳高度
* 不平衡 → 回傳 `-1`

這個 `-1` 的用意是「一旦下面不平衡，上面直接停」，不用再做多餘計算

---

### 2. 空節點的高度視為 0

如果 `x == nullptr`

* 代表是一棵空樹
* 高度直接當作 `0`

---

### 3. 遞迴拿左子樹結果，先檢查是否已經失敗

`l = check(x->left)`
如果 `l == -1`

* 代表左子樹已經不平衡
* 直接回傳 `-1`（不用再算右邊）

---

### 4. 遞迴拿右子樹結果，先檢查是否已經失敗

`r = check(x->right)`
如果 `r == -1`

* 代表右子樹已經不平衡
* 直接回傳 `-1`

---

### 5. 檢查高度差是否超過 1，決定回傳高度或 -1

如果 `abs(l - r) > 1`

* 代表這個節點不平衡 → 回傳 `-1`

否則

* 代表這個節點平衡 → 回傳高度 `max(l, r) + 1`

---

### 6. `isBalanced(root)` 只要檢查根節點回傳值是否為 -1

如果 `check(root) != -1` → 回傳 `true`
否則回傳 `false`

## 💻 程式碼實作

/**
 * 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:
    int check(TreeNode* x) {
        if (!x) {
            return 0;
        }
        int l = check(x->left);
        if (l == -1) {
            return -1;
        }
        int r = check(x->right);
        if (r == -1) {
            return -1;
        }
        if (abs(l - r) > 1) {
            return -1;
        };
        return max(l, r) + 1;
    }
    bool isBalanced(TreeNode* root) {
        return (check(root) != -1);
    }
};

## 🔗 題目連結
https://leetcode.com/problems/balanced-binary-tree/description/