平衡因子是左子树高度减右子树高度，因禁止存储高度，需现场递归计算：getheight(node) 返回空节点-1、非空节点max(左右子树高度)+1；getbalancefactor(node) 入口先判空，再调用getheight。
平衡因子定义与为什么不能直接用高度
平衡因子是左子树高度减右子树高度，但题目明确「不使用高度记录」——意味着你不能在节点里存 height 字段，也不能在插入/删除时维护它。这时候必须现场计算子树高度，否则无法得出平衡因子。这不是偷懒，而是某些场景（比如只做一次性检查、调试验证、或教学演示）下刻意剥离状态依赖的约束。
如何现场计算子树高度（无缓存）
每次调用 getBalanceFactor(node) 时，都得递归算左右子树最大深度。注意：这不是 AVL 树的高效实现方式，只是满足“不记录高度”的硬性要求。关键点在于写一个纯函数式 getHeight(node)，它不修改节点，也不依赖任何预存值：
int getHeight(TreeNode* node) {
if (!node) return -1; // 空节点高度为 -1（按边数定义）或 0（按节点数定义），统一即可
return std::max(getHeight(node->left), getHeight(node->right)) + 1;
}
然后平衡因子就是：
int getBalanceFactor(TreeNode* node) {
if (!node) return 0;
return getHeight(node->left) - getHeight(node->right);
}
-
getHeight时间复杂度是 O(n)，对单个节点调用会遍历其整个子树 - 整棵树调用一次
getBalanceFactor（比如检查根节点），最坏 O(n)；若遍历所有节点检查是否平衡，则总代价 O(n²) - 务必统一高度定义：空节点返回 -1（对应边数）更常见，避免和叶子节点高度 0 混淆
实际调用时容易漏掉的边界
直接套公式 getHeight(left) - getHeight(right) 看似简单，但真实代码里常因这几处出错：
- 忘记判空：如果
node本身为nullptr，node->left会崩溃 →getBalanceFactor入口必须先判空 - 高度定义不一致：有的教材把叶子高度定为 1，有的定为 0，混用会导致平衡因子差 1 → 全局统一用
nullptr → -1 - 误以为“平衡因子=0 就一定平衡”：AVL 要求每个节点平衡因子 ∈ {-1, 0, 1}，但仅检查根不够，必须逐节点判断
- 递归爆栈风险：极端偏斜树（链状）下
getHeight递归深度 = 节点数，可能栈溢出 → 生产环境必须改迭代或加深度限制
要不要真这么干？
纯理论可行，但实践中几乎没人这么用。AVL 树之所以高效，全靠每个节点缓存 height（或等价的 balance），让 getBalanceFactor 变成 O(1)。现场算高度只适合验证逻辑、单元测试、或极小数据集。一旦树节点超百，O(n²) 检查就明显卡顿。真正要落地，还是得加字段、改插入逻辑——但题目限定不许，那就老老实实递归算，别试图“优化”掉递归。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
