---

概念

平衡樹(Balance Tree，BT) 指的是，任意節點的子樹的高度差都小于等于1。

常見的符合平衡樹的有：

• B樹（多路平衡搜索樹）
• AVL樹（二叉平衡搜索樹）
• 紅黑樹 （自平衡二叉查找樹），AVL樹的特化

代碼實現判斷一棵二叉樹是否為平衡樹

從上到下判斷（DFS先序遍歷）

depth 函數計算當前節點cur的深度：

• 返回值： 通過后序遍歷的方式實現深度計算。
• 終止條件： 空節點深度為0。

isBalanced 函數實現判斷：

• 返回值： 先判斷 當前子樹 是不是平衡樹，再判斷 左右子樹 是不是平衡樹（先序遍歷遞歸（根左右））。
• 終止條件： 空節點當然是平衡樹。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {int depth(TreeNode* cur){ // 計算cur深度if(!cur) return 0;return max(depth(cur->right), depth(cur->left)) + 1;}
public:bool isBalanced(TreeNode* root) {if(root == nullptr) return true;return abs(depth(root->left) - depth(root->right)) <=1 && isBalanced(root->left) && isBalanced(root->right);}
};

從下到上判斷（DFS后序遍歷）

fun 函數實現后序遍歷+剪枝：

• 返回值：

1. 當 cur 的左 / 右子樹的深度差 ≤1 時：表明 當前子樹仍為平衡樹，返回當前子樹的深度，即 左 / 右子樹的深度最大值 +1（ max(left, right) + 1 ）， ；
2. 當 左 / 右子樹的深度差 >1 時 ：則返回 -1 （也可以是其他負值，主要用來標明 此子樹不是平衡樹 ，方便后續剪枝 ）。

• 終止條件：

1. 當 cur 為空：說明越過葉節點，因此返回高度 0 ；
2. 當左（右）子樹深度為 ?1 ：代表此樹的 左（右）子樹 不是平衡樹，可行性剪枝，直接返回 ?1 ；

isBalanced 函數實現判斷：

• 返回值： 若 fun(root) != -1 ，則說明此樹平衡，返回 true ； 否則返回 false 。

class Solution { // 后序遍歷+剪枝int fun(TreeNode* cur){if(!cur) return 0;int left = fun(cur->left);if(left==-1) return -1; // 剪枝int right = fun(cur->right);if(right==-1) return -1; // 剪枝return abs(left-right) < 2 ? max(left, right) + 1 : -1;}
public:bool isBalanced(TreeNode* root) {if(root == nullptr) return true;;return fun(root)!=-1;}
};