二叉树高度递归计算核心是：空节点返回0，非空返回1+max(左子树高度,右子树高度)；必须判空防崩溃，禁用全局变量；BFS可避免栈溢出但空间开销大；需严格统一“节点数”或“边数”定义。
递归计算二叉树高度的核心逻辑
二叉树的高度（深度）定义为从根节点到最远叶子节点的最长路径上的边数，或节点数——实际编码中需先明确约定。C++ 常见实现默认返回节点数（即根为 1 层），对应公式：height(root) = 1 + max(height(root->left), height(root->right))，空节点返回 0。
关键点在于：必须对左右子树分别递归，取较大值，再加 1；不能只遍历一边，也不能漏掉空指针判别。
- 空节点必须返回
0（若按“边数”定义则返回-1，但多数教材和 OJ 默认节点计数） - 递归调用前务必检查
root是否为空，否则访问root->left会触发段错误 - 不要在递归里维护全局变量或传引用计数——易错且破坏函数纯性
标准实现与常见错误写法对比
正确写法简洁直接：
int height(TreeNode* root) {
if (!root) return 0;
return 1 + std::max(height(root->left), height(root->right));
}典型错误包括：
立即学习“C++免费学习笔记（深入）”；
- 忘记空指针检查，直接写
height(root->left)→ 运行时崩溃 - 写成
return height(root->left) + height(root->right) + 1→ 计算的是“宽度相关量”，不是高度 - 用
if (root == nullptr)判空但拼错为if (root = nullptr)→ 意外赋值，逻辑恒真 - 返回类型用
void配合参数引用输出 → 增加调用复杂度，无必要
非递归方式（BFS 层序遍历）适用场景
当树可能极深（如退化为链表）、担心栈溢出时，递归版有风险。此时改用 BFS 按层扫描更稳妥，时间 O(n)，空间 O(w)，w 为最大层宽。
核心思路：每处理完一层，高度 +1。用 queue 实现：
int height(TreeNode* root) {
if (!root) return 0;
queue q;
q.push(root);
int h = 0;
while (!q.empty()) {
int sz = q.size();
h++;
for (int i = 0; i < sz; ++i) {
auto node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return h;
} - BFS 版天然避免递归栈限制，适合生产环境或超深树
- 比 DFS 递归多用内存，尤其满二叉树下队列峰值达 O(2^h)
- 不能提前退出——必须遍历到最后一层才知高度，而递归在回溯中自然得到最大值
LeetCode 或本地测试时要注意的细节
不同题目对“高度”定义可能不一致。例如 LeetCode #104 明确要求“maximum depth”，定义为节点数；但某些面试题或教材可能以边数为准（根到叶子的边数），此时空树高为 0，单节点高为 0。
- 务必先读清题干中
depth或height的定义，再决定 base case 返回0还是-1 - 若用
std::max，需包含std::max({a,b})，但两参数版更通用 - TreeNode 结构体若未定义，常见为：
struct TreeNode { int val; TreeNode *left; TreeNode *right; };，注意指针初始化为nullptr而非NULL
真正容易被忽略的，是定义一致性——同一项目里混用“节点数高度”和“边数高度”，会导致父子节点高度关系错乱，调试时极难定位。
