LeetCode验证二叉搜索树

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

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

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

示例 1：

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

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

提示：

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

本题思路

其实本题需要懂得二叉搜索树的特殊性，其实我们只需要遍历二叉树，然后两个标记，一个最大和一个最小，我们划分出区段，也就是下面的值必须在这个区段才符合规则，如果不满足即返回false

接下来，问题就是我们如何知道范围为多少，其实也很好理解，如果是左子树，那么下面肯定是越来越小，那最大值其实就是上一个父节点的值，如果是右子树，那么下面肯定是越来越大，那么最小值其实也是上一个父节点，按照这个约束向下约束即可

下面上代码

class Solution {
    
    public boolean isValidBST(TreeNode root) {
        return isValid(root,null,null);
    }
 
    public boolean isValid(TreeNode p,Integer max,Integer min){
        if(p==null){
            return true;
        }
//如果不为空就比较
        if(min!=null&&p.val<=min){
            return false;
        }
        if(max!=null&&p.val>=max){
            return false;
        }
//所有子树的子树也是二叉搜索树
        return isValid(p.left,p.val,min)&&isValid(p.right,max,p.val);
    }
}

其实到现在我们也就可以发现一件事，那就是如果以父节点为界的话左边小于它，右边大于他，如果是一棵二叉搜索树的话，那么其中序遍历的结果就一定是升序的，那么这边就有第二种解法，中序遍历出序列，而后检查是否为升序，即可判断。这边博主就不贴出代码了，感兴趣的小伙伴可以试试看哦。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。