平衡BST需每个节点左右子树高度差≤1，应后序遍历中一次性返回是否平衡和高度，用std::pair避免重复计算，空节点高度为-1，失衡时立即短路返回。
如何用递归判断 BST 是否平衡
BST 平衡的定义是：对每个节点，其左子树与右子树的高度差 ≤ 1。注意，**平衡性不依赖于 BST 的有序性，只依赖结构高度**——哪怕你把一棵 BST 的键全删了、只留空壳，只要左右高差超 1，它就不平衡。
核心思路是后序遍历：先算左右子树高度，再比差值，最后向上返回当前子树高度。关键点在于——不能分开调用 height(root->left) 和 height(root->right) 两次，否则时间退化到 O(n²)。
- 正确做法：在一次递归中同时返回「是否平衡」和「当前子树高度」，可用
std::pair或自定义结构体 - 空节点高度定义为 -1（这样叶子节点高度才是 0），统一处理边界
- 一旦某子树失衡，直接短路返回，不必继续算高度
为什么不能只写一个 getHeight() 再套用 abs(getHeight(l)-getHeight(r))
这种写法看似简洁，但会重复遍历大量节点。例如根节点调用时，getHeight(root->left) 遍历整个左子树；紧接着 getHeight(root->right) 又遍历右子树；而检查左子节点时，又会再次调用它的左右 getHeight……最坏情况总时间复杂度达 O(n log n) 甚至 O(n²)（退化成链表时）。
真正高效的解法必须避免重复计算。观察发现：每个节点只需被访问一次，且其高度信息可由子节点“上推”而来。
- 错误示例：
isBalanced(root) { return abs(getHeight(root->left) - getHeight(root->right)) left) && isBalanced(root->right); } - 问题根源：
getHeight每次都从头递归到底，未复用中间结果 - 修复方向：把高度计算和平衡判断合并在同一趟遍历中完成
std::pair 在平衡判定中的实际用法
这是 C++ 中最轻量且清晰的返回组合方式：第一个元素表示以当前节点为根的子树是否平衡，第二个表示该子树高度。
return checkBalance(root).first;
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
