C++实现二叉树高度与最小值计算时出现段错误的问题咨询

段错误触发逻辑 #

• 空节点判断不是只处理整棵树为空的边缘场景。递归遍历过程中，每个非叶子节点必然带有至少一个空的子节点，递归调用时会直接把nullptr传入函数参数。
• 原函数入口未做空判断，直接访问root->leftChild、root->rightChild，一旦传入nullptr就会触发空指针解引用，抛出段错误，和整棵树是否有节点无关。

两个方法的逻辑偏差 #

树高计算 #

• 补充空节点返回-1后结果正确，本质是契合二叉树高度的通用定义：空树高度为-1，叶子节点高度为1 + max(-1, -1) = 0，递推逻辑自洽。原代码中“判断是否为叶子节点返回0”的分支完全冗余，靠统一递归逻辑就能输出正确结果。

任意二叉树最小值计算 #

• 空节点的返回值不能随意设置。之前返回-1出错的原因是：-1是合法的int类型值，会参与std::min的比较，相当于在不存在的空节点上虚拟了一个值为-1的节点，最终结果必然错误。
• 该函数的语义是「计算子树内所有真实节点的最小值」，空节点无对应有效值，为了不干扰最小值比较，空节点需要返回一个大于所有可能树内节点值的数值，这样min计算时会自动跳过空节点的返回值。

代码修正 #

首先补充依赖头文件：

#include <limits>

修正后的树高递归实现：

int height(Node *root)
{
    if (root == nullptr)
        return -1;
    return 1 + std::max(height(root->leftChild), height(root->rightChild));
}

修正后的任意二叉树最小值递归实现：

int minimum(Node *root)
{
    if (root == nullptr)
        return std::numeric_limits<int>::max();
    return std::min({
        minimum(root->leftChild),
        minimum(root->rightChild),
        root->value
    });
}

注意要点 #

• 递归函数的空节点返回值必须和函数语义匹配，不能随意赋值：
  • 计算子树高度时，空节点返回-1，匹配高度递推关系
  • 求子树最小值时，空节点返回int类型最大值，避免干扰min比较
  • 求子树最大值时，空节点返回int类型最小值，同理不干扰max比较
• 原代码中判断“是否为叶子节点”的分支可以全部移除，统一的递归逻辑即可覆盖所有场景，减少冗余判断。

内容的提问来源于stack exchange，提问作者Naveen Kumar Narsupalli