C++如何实现二叉树的深度计算_C++递归求树的高度算法实现【练习】-C++

二叉树高度递归计算核心是：空节点返回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++免费学习笔记（深入）”；