平衡BST需每个节点左右子树高度差≤1，应后序遍历中一次性返回是否平衡和高度，用std::pair避免重复计算，空节点高度为-1，失衡时立即短路返回。
如何用递归判断 BST 是否平衡
BST 平衡的定义是：对每个节点，其左子树与右子树的高度差 ≤ 1。注意，**平衡性不依赖于 BST 的有序性，只依赖结构高度**——哪怕你把一棵 BST 的键全删了、只留空壳，只要左右高差超 1，它就不平衡。
核心思路是后序遍历：先算左右子树高度，再比差值，最后向上返回当前子树高度。关键点在于——不能分开调用 height(root->left) 和 height(root->right) 两次，否则时间退化到 O(n²)。
- 正确做法：在一次递归中同时返回「是否平衡」和「当前子树高度」，可用
std::pair<bool int></bool>或自定义结构体 - 空节点高度定义为 -1（这样叶子节点高度才是 0），统一处理边界
- 一旦某子树失衡，直接短路返回，不必继续算高度
为什么不能只写一个 getHeight() 再套用 abs(getHeight(l)-getHeight(r))
这种写法看似简洁，但会重复遍历大量节点。例如根节点调用时，getHeight(root->left) 遍历整个左子树；紧接着 getHeight(root->right) 又遍历右子树；而检查左子节点时，又会再次调用它的左右 getHeight……最坏情况总时间复杂度达 O(n log n) 甚至 O(n²)（退化成链表时）。
真正高效的解法必须避免重复计算。观察发现：每个节点只需被访问一次，且其高度信息可由子节点“上推”而来。
立即学习“C++免费学习笔记（深入）”；
- 错误示例：
isBalanced(root) { return abs(getHeight(root->left) - getHeight(root->right)) left) && isBalanced(root->right); } - 问题根源：
getHeight每次都从头递归到底，未复用中间结果 - 修复方向：把高度计算和平衡判断合并在同一趟遍历中完成
std::pair<bool int></bool> 在平衡判定中的实际用法
这是 C++ 中最轻量且清晰的返回组合方式：第一个元素表示以当前节点为根的子树是否平衡，第二个表示该子树高度。
std::pair<bool, int> checkBalance(TreeNode* node) {
if (!node) return {true, -1}; // 空节点视为平衡，高度-1
auto [l_bal, l_h] = checkBalance(node->left);
if (!l_bal) return {false, 0}; // 左子树已失衡，直接退出
auto [r_bal, r_h] = checkBalance(node->right);
if (!r_bal) return {false, 0};
int diff = std::abs(l_h - r_h);
bool cur_bal = (diff <= 1);
int cur_h = std::max(l_h, r_h) + 1;
return {cur_bal, cur_h};
}
调用入口：return checkBalance(root).first;
- 使用结构化绑定（C++17）让代码可读性大幅提升，避免手动取
.first/.second - 所有非空节点的高度都是
max(left_height, right_height) + 1，严格按定义实现 - 提前剪枝逻辑放在获取左右结果之后、计算当前差值之前，确保不遗漏任一失衡点
容易忽略的边界：空树、单节点、只有左/右孩子的树
这些情况必须显式覆盖，否则容易在指针解引用或高度比较时出错。
- 空树：
root == nullptr→ 直接返回{true, -1}，这是递归基，不可省略 - 单节点：左右均为
nullptr，左右高度都是 -1，差值为 0 → 平衡，高度为 0 - 只有左孩子：右子树高度为 -1，左子树高度为 0 → 差值为 1 → 合法平衡
- 若误将空节点高度设为 0，则单节点左右高度都为 0，看似没问题；但当节点只有左孩子时，左高=1、右高=0 → 差=1，仍对；但更深层会出现偏差，比如祖父节点计算时多加了一层，导致整体高度偏高，最终差值误判
高度定义为 -1 是行业通用做法，和树高（number of edges）定义一致，别为了“看起来顺眼”改成 0。
