【五种方法】判断一棵二叉树是否为二叉搜索树_编写一个算法,判别给定的二叉树是否是二叉搜索树

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
文章字体风格：
红色文字表示：重难点
蓝色文字表示：思路以及想法
　
如果大家觉得有帮助的话，感谢大家帮忙点赞！收藏！转发！

二叉搜索树的概念

在二叉树中，左孩子节点小于根节点，右孩子节点大于根节点，这样的树叫做二叉搜索树【关键点：注意根节点的左半部分一定全部都小于根节点；根节点的右半部分一定全部都大于根节点。】

判断二叉搜索树的方法

1. 方法１(错误示范)

//对于每个节点，检测它的左孩子节点是否小于它，且右孩子节点是否大于它。
bool isBST(node* root)
{
  if (root == NULL)
    return true;

  //如果左孩子大于根节点，则不是BST
  if (root->left != NULL && root->left->key> root->key)
    return false;

  //如果右孩子节点小于根节点，则不是BST
  if (root->right != NULL && root->right->key < root->key)
    return false;

  //递归的判断
  if (!isBST(root->left) || !isBST(root->right))
    return false;

  //BST
  return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个代码就犯了上面红色标注的错误
错误图如下

2. 方法２(每次比较的时候，去找该节点以下的最大最小值进行比较)

根据最基础的定义，我们在判断每棵子树的时候返回左子树的最大值小于当前节点值，同时右子树的最小值大于当前节点值，是的，这样会出现某些节点进行多次判断，当然我们可以通过添加数组结构来保存中间结果加快计算

二叉树的最大值出现在最右侧的位置，最小值出现在最左侧的部分

int maxValue(node* root)
{
    if(root == NULL)
        return INT_MAX
    while(root -> right)
        root = root -> right;
    return root -> value;
}
int minValue(node* root)
{
    if(root == NULL)
        return INT_MIN
    while(root -> left)
        root = root -> left;
    return root -> value;
}
bool isBST(node* root )
{
        if (root == NULL)
               return true;
        //如果左子树最大值大于根节点，则返回false
        if (root->left != NULL && maxValue(root->left) > node->value)
               return false;
        //如果右子树最小值小于根节点，则返回false
        if (root->right != NULL && minValue(root->right) < node->value)
               return false;

        //递归判断
        if (!isBST(root->left) || !isBST(root->right))
               return false;
        return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3. 方法3（中序遍历二叉树，把遍历结果存储到数组，判断数组是否增序）

void LDR(node * root, vector<int>& inorder)
{
    if(root == NULL)
        return;
    LDR(root -> left);
    inorder.push_back(root -> value);
    LDR(root -> right);
}
bool isBST(node* root)
{
    vector<int> inorder;
    LDR(root);
    for(int i = 1; i < inorder.size(); ++i)
        if(inorder[i - 1] >= inorder[i])
            return false;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 方法4（中序遍历，在函数外定义一个变量，遍历过程中每次去比较前一个值）

//保存之前访问过的节点的值，判断当前访问的小于之前保存的值
int lastVisited = INT_MIN;
bool isBST(node * root)
{
    if(root == NULL)
        return true;
    //判断左子树
    if(!LDR(root -> left))
        return false;
    if(root -> value <= lastVisited)
        return false;
    lastVisited = root -> value;
    //判断右子树
    if(!LDR(root -> right))
        return false;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

5. 方法５ (前序遍历正好是比较搜索树的顺序)

bool isBST(node *root, int maxVal, int minVal)  
{  
    if (root == NULL)  
        return true;  
    if (root->val < minVal || root->val >= maxVal)  
        return false;  
    if (!preOrder(root->left, root->val, minVal) || !preOrder(root->right, maxVal, root->val))  
        return false;  
    return true;  
}  
isBST(root, INT_MAX, INT_MIN);
1
2
3
4
5
6
7
8
9
10
11