📘 題目敘述
給你一棵二元樹 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/