递归计算二叉树高度：空树返回值错误问题求助

嘿，我一眼就瞅出你代码里的核心问题啦——你没处理当前节点为空的终止情况，反而错误地把“子树为空”当成了终止条件，这才导致空树高度不对，改了又牵一发而动全身。

先给你理清楚正确的递归逻辑：

• 空节点（空树）的高度是0，这是递归的最底层终止条件
• 非空节点的高度 = 左右子树高度的最大值 + 1（加上当前节点这一层）

再看看你原代码的问题：
你一开始就直接访问n->right和n->left，如果传入的是空节点（空树的情况），这直接会触发空指针异常！而且你的if(n->right == NULL || n->left == NULL)条件完全不符合递归逻辑——哪怕只有一个子树存在，你也应该继续递归计算那个子树的高度，而不是直接返回1。

现在给你修改后的正确代码：

#include <algorithm> // 需要引入这个头文件来用std::max

int BTree::recursive_height_helper(BSTNode *n) {
    // 终止条件：空节点高度为0，完美解决空树返回0的需求
    if (n == NULL) {
        return 0;
    }
    // 递归计算左右子树的高度
    int rHeight = recursive_height_helper(n->right);
    int lHeight = recursive_height_helper(n->left);
    // 返回左右子树的最大高度 + 当前节点所在的这一层
    return std::max(rHeight, lHeight) + 1;
}

解释下关键修改点：

1. 新增了空节点判断作为递归终止条件——这直接解决了空树高度返回0的问题
2. 删掉了原来错误的子树为空判断，不管子树是否为空，递归都会自动处理（空的话返回0）
3. 用std::max取左右子树高度的最大值再加1，这才是二叉树高度的正确计算逻辑（高度是从根到最远叶子节点的层数）

这样修改后，空树返回0，单节点树返回1，多层树也能精准计算高度啦～

内容的提问来源于stack exchange，提问作者user9573040