高效判断二叉树是否为二叉搜索树的算法

高效判断二叉树是否为二叉搜索树的算法

本文介绍了一种高效的算法，用于判断一棵二叉树是否为二叉搜索树。算法采用深度优先搜索的方式，在遍历过程中判断每个节点是否满足二叉搜索树的定义。

算法设计思想

1. 二叉搜索树的特点是，对于每个节点，其左子树的所有节点的值都小于该节点的值，右子树的所有节点的值都大于该节点的值。
2. 采用深度优先搜索的方式遍历二叉树，在遍历的过程中，对于每个节点，判断其是否满足上述条件。

C语言描述算法的关键部分

// 定义二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 辅助函数，判断以root为根节点的子树是否为二叉搜索树
bool isValidBSTHelper(struct TreeNode* root, struct TreeNode* minNode, struct TreeNode* maxNode) {
    // 当前节点为空，满足二叉搜索树定义
    if (root == NULL) {
        return true;
    }
    // 当前节点的值小于等于左子树的最大值，不满足二叉搜索树定义
    if (minNode != NULL && root->val <= minNode->val) {
        return false;
    }
    // 当前节点的值大于等于右子树的最小值，不满足二叉搜索树定义
    if (maxNode != NULL && root->val >= maxNode->val) {
        return false;
    }
    // 递归判断左子树和右子树是否为二叉搜索树
    return isValidBSTHelper(root->left, minNode, root) && isValidBSTHelper(root->right, root, maxNode);
}

// 判断二叉树是否为二叉搜索树
bool isValidBST(struct TreeNode* root) {
    // 初始时，左子树的最大值和右子树的最小值都为空
    return isValidBSTHelper(root, NULL, NULL);
}

注：以上代码中，假设二叉树中的节点值不重复。若存在重复值，可以根据具体需求做相应修改。