98. 验证二叉搜索树

1.题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

提示：

• 树中节点数目范围在[1, 104] 内
• $-2^{31}$ <= Node.val <= $2^{31}-1$

2.示例

输入：root = [2,1,3]
输出：true
1
2

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
1
2
3

3.答案

①中序遍历

在二叉搜索树中，左子树所有的值小于根，根的值小于右子树。而中序遍历的顺序是 左根右，可见二叉搜索树的中序遍历序列是一个有序序列。可以由此判断二叉搜索树是否有效。

   void inorder(TreeNode* root,vector<int> &res){  //中序遍历
        if(!root) return ;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    bool isValidBST(TreeNode* root) {
        vector<int> res;
        inorder(root,res);
        for(int i=0;i<res.size()-1;i++){
            if(res[i]>=res[i+1]) return false;  //如果不是有序序列
        }
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

②递归

左子树上所有的点小于根，右子树上所有的点大于根，，所以是每个结点的值都在一个区间内，而不是单纯地小于右孩子和大于左孩子。
根据要求 $-2^{31}$ <= Node.val <= $2^{31}-1$，
而INT_MAX=$2^{31}-1$,INT_MIN=$-2^{31}$ ，所以Int类型没办法将所有节点可能取值包含，如果节点取 INT_MAX,INT_MIN就无法正确判断。
所以最开始的区间范围是 [LONG_MIN,LONG_MAX], 对应的上下界 l,r 的类型也应该是long.

 // 递归检查，，
    bool qujian(TreeNode *root,long  l,long r){  //root子树应在的大小区间内
        if(!root) return true;
        // 当前结点在区间内
        if(l>=root->val||root->val>=r)   return false;  //根在区间内
        return qujian(root->left,l,root->val)&&qujian(root->right,root->val,r);  //左右子树均在区间内
       
    }
    bool isValidBST(TreeNode* root) {
       return qujian(root,LONG_MIN,LONG_MAX);
    }

1
2
3
4
5
6
7
8
9
10
11
12

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/validate-binary-search-tree