C++二叉搜索树验证递归函数崩溃问题排查求助

崩溃直接原因 #

你的isValidBST递归函数没有处理node为NULL的边界场景。当递归遍历到叶子节点时，它的左/右子节点是NULL，此时调用isValidBST(NULL)，函数内部会直接执行node->getLeft()这类操作——空指针解引用会直接导致程序崩溃。

修复步骤 #

1. 补充空节点边界判断 #

在函数最开头添加判断：如果传入的node是NULL，直接返回true（空树本身是合法的二叉搜索树）。

2. 修复BST验证逻辑的根本性缺陷 #

另外需要注意，你当前的验证逻辑只检查了直接子节点与当前节点的大小关系，这并不够。合法的BST要求：

• 左子树的所有节点值都小于当前节点值
• 右子树的所有节点值都大于当前节点值

仅检查直接子节点会漏掉深层子树的非法情况，比如某个节点的右子树中存在比根节点小的节点，你的代码会误判为合法。因此需要通过传递上下界的方式，递归验证每个节点的取值范围。

修正后的完整代码 #

Node类（无需修改） #

#include <iostream>

class Node
{
public:
   Node(int value, Node* left, Node* right)
   {
      this->value = value;
      this->left = left;
      this->right = right;
   }

   int getValue() const
   {
      return value;
   }

   Node* getLeft() const
   {
      return left;
   }

   Node* getRight() const
   {
      return right;
   }

private:
   int value;
   Node* left;
   Node* right;
};

修正后的BinarySearchTree类 #

#include <climits> // 需包含此头文件使用LLONG_MIN/LLONG_MAX

class BinarySearchTree
{
private:
    // 辅助递归函数，传递当前节点的取值上下界
    static bool isValidBSTHelper(const Node* node, long long lowerBound, long long upperBound) {
        // 空节点合法
        if (node == nullptr) {
            return true;
        }
        int val = node->getValue();
        // 当前节点值超出上下界则非法
        if (val <= lowerBound || val >= upperBound) {
            return false;
        }
        // 递归验证左子树：左子树所有节点必须小于当前节点值，下界不变，上界设为当前节点值
        if (!isValidBSTHelper(node->getLeft(), lowerBound, val)) {
            return false;
        }
        // 递归验证右子树：右子树所有节点必须大于当前节点值，上界不变，下界设为当前节点值
        return isValidBSTHelper(node->getRight(), val, upperBound);
    }

public:
    static bool isValidBST(const Node* node) {
        // 初始上下界用long long避免int溢出问题
        return isValidBSTHelper(node, LLONG_MIN, LLONG_MAX);
    }   
};

主函数（无需修改） #

int main()
{
   Node n1(1, NULL, NULL);
   Node n3(3, NULL, NULL);
   Node n2(2, &n1, &n3);

    std::cout << " TEST ";
    std::cout << BinarySearchTree::isValidBST(&n2);
    std::cout << " DONE " ;

    return 0;
}

说明 #

• 用LLONG_MIN和LLONG_MAX作为初始上下界，避免了int类型取值范围溢出的问题
• 辅助函数传递上下界，确保每个节点的取值都在合法范围内，彻底修复了原逻辑的漏洞
• 空节点的判断直接解决了递归崩溃的核心问题

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