基于递归中序遍历的BST验证：static prev作用及左子树判断疑问

给定代码 #

二叉树节点结构 #

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

BST验证递归代码 #

int isBST(struct  node* root){
    static struct node *prev = NULL;
    if(root!=NULL){
        if(!isBST(root->left)){
            return 0;
        }
        if(prev!=NULL && root->data <= prev->data){
            return 0;
        }
        prev = root;
        return isBST(root->right);
    }
    else{
        return 1;
    }
}

问题解答 #

问题1：为何将节点指针prev声明为static类型？ #

• 这段代码是靠中序遍历验证BST的——正常BST的中序遍历结果是严格递增的，prev用来记录上一个被访问的节点，这样才能和当前节点的值做大小比较。
• 如果不用static，每次递归调用isBST都会新建一个prev变量，初始值是NULL，根本没法持续记录上一个节点的信息，整个比较逻辑直接失效。
• 不过这种写法有个坑：如果多次调用isBST，prev会保留上一次调用的残留值，可能导致验证出错，得每次调用前手动把prev重置为NULL。

问题2：代码中if(!isBST(root->left)){return 0;}这段逻辑在什么情况下会返回0？ #

这段代码是递归检查左子树是否符合BST规则，只要左子树本身不满足BST的要求，就会返回0终止验证。具体场景包括：

• 左子树里某个节点的左孩子值比该节点大
• 左子树里某个节点的右孩子值小于等于该节点
• 左子树的中序遍历结果不是严格递增的（比如左子树里有节点值比它的祖先节点还大）
• 说白了，只要左子树内部不符合BST定义，或者左子树的最大节点值超过当前节点值，这段递归就会返回0。

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