C语言判断给定树是否为二叉搜索树代码遇段错误求助

段错误的根源 #

你代码里直接访问root->left->val和root->right->val时，完全没检查root->left或root->right是不是NULL。比如碰到叶子节点（左右子节点都是空），或者某个节点只有左/右子节点时，解引用空指针必然触发段错误——这是C语言里最常见的内存非法访问问题之一。

额外的逻辑漏洞 #

除了段错误，你的BST判断逻辑也不对。二叉搜索树要求左子树所有节点的值都小于当前节点，右子树所有节点的值都大于当前节点，不是只检查直接子节点就行。举个反例：

5
   / \
  3   7
     /
    4

这个树里4比5小，但你的代码只会检查5>3、5<7、7>4，根本不会发现4违反了BST规则，会错误地认为这是合法BST。

修复后的完整代码 #

下面是修正后的代码，既解决了段错误，又符合BST的严格定义：

#include <limits.h>

struct node {
    int val;
    struct node *left;
    struct node *right;
};

// 递归辅助函数，传递当前子树允许的取值范围
int isBSTHelper(struct node* root, int minVal, int maxVal) {
    if (root == NULL) {
        return 1;
    }
    // 当前节点值超出允许范围，直接返回0
    if (root->val <= minVal || root->val >= maxVal) {
        return 0;
    }
    // 左子树的最大值是当前节点值，右子树的最小值是当前节点值
    return isBSTHelper(root->left, minVal, root->val) && isBSTHelper(root->right, root->val, maxVal);
}

// 对外调用的接口，初始范围设为int的极值
int isBST(struct node* root) {
    return isBSTHelper(root, INT_MIN, INT_MAX);
}

修复要点 #

• 先判断root是否为空，避免空指针解引用，彻底解决段错误；
• 用辅助函数传递取值范围，确保整个左/右子树都符合BST的大小规则；
• 使用INT_MIN和INT_MAX作为初始边界，覆盖int类型的所有可能取值。

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