如何修改中序遍历函数实现二叉树是否为BST的合法性校验

二叉搜索树的核心性质是其中序遍历结果为严格递增序列，因此无需打印全量节点，只需在中序遍历过程中校验相邻节点值的大小关系即可完成合法性判断。

你可以将原有打印节点的中序遍历函数改造为如下校验逻辑：

#include <limits.h>

// 递归校验函数，prev为上一个遍历到的节点值的指针，初始传入极小值地址
int is_valid_bst(struct node *root, int *prev) {
    // 空节点视为合法
    if (root == NULL) {
        return 1;
    }
    // 先校验左子树，左子树非法直接返回
    if (!is_valid_bst(root->left_child, prev)) {
        return 0;
    }
    // 校验当前节点值是否满足严格大于上一个节点值
    if (root->data <= *prev) {
        return 0;
    }
    // 更新上一个节点值为当前节点值
    *prev = root->data;
    // 校验右子树
    return is_valid_bst(root->right_child, prev);
}

// 对外调用入口
void check_bst(struct node *root) {
    int prev = INT_MIN;
    if (is_valid_bst(root, &prev)) {
        printf("The binary tree is a BST\n");
    } else {
        printf("The binary tree is not a BST\n");
    }
}

注意事项 #

• 如果你的节点值可能包含INT_MIN，可以将prev的初始值替换为对应类型的极小值，或者改用指针记录上一个节点的地址而非值，避免边界值误判
• 该方案时间复杂度为O(n)，空间复杂度为树的高度（递归栈开销），针对100万量级的节点，平衡树场景下完全无性能问题；如果树退化为链表会有栈溢出风险，该场景可以改用迭代版中序遍历实现
• 不要使用静态变量存储prev值，会导致多次调用函数时出现状态残留问题

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