98 BST及其验证

BSTBinarybinary search tree,二叉搜索树,Also known as a binary sorted tree,When using in-order traversal on it, you can get an increasing sequence.

题目描述

给定一个二叉树,判断其是否是一个有效的二叉搜索树

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数.

节点的右子树只包含大于当前节点的数.

所有左子树和右子树自身必须也是二叉搜索树.

示例

输入：

2
/
1 3

输出：true

输入：

​ 5

/ \

1 4

​ / \

​ 3 6

输出：false

解释：根节点的值为5,But the value of its right child is 4,The condition that the value of all nodes in the right subtree is greater than the root node is not satisfied

题目解析

   Depth-first search based on topic prompts,It can be written recursively.It is enough to judge each time whether the left and right subtrees satisfy the conditions of the binary search tree;

All nodes of the left subtree have values ​​less than the value of the root node

The value of all nodes in the right subtree is greater than the value of the root node

  But it's not just comparing the values ​​of the root node and the left and right nodes to meet the conditions,It is to satisfy the condition on the entire binary tree,Therefore, there should be a bounded range for the value of each node,例如：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hCymzVOj-1601715451019)(D:\我的博客\刷题\img\leetCode98图示1.png)]

  So return when recursivefalseYou can't just compare the size of the left and right nodes with the parent node,How to do it is only understood after reading the code of the big guy,代码如下：

public boolean isBST(TreeNode root, long min, long max) {
    
    if (root == null) {
    
        return true;
    }

    if (root.val <= min || root.val >= max) {
    
        return false;
    }
    return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
}

public boolean isValidBST(TreeNode root) {
    
    if (root == null) {
    
        return true;
    }
    return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

实现思路如下：

1. First use a maximum value and a minimum value as the boundary judgment conditions,Make sure that the root node value of the entire tree is within this range,这里使用LongThe maximum value of the type is because there is a test case when the code is submittedint类型的最大值,导致错误.

2. The program enters firstisBST函数时,对于

   root.val <= min || root.val >= max
   

   该条件的bool值为真.Then enter the following recursive condition.

3. And this recursion is also set very concise,for the node of the left subtree,The minimum value of its bounds is unchanged,The maximum value is set to the value of the current node,That is, the node of the left subtree cannot be greater than the value of the current node;for nodes in the right subtree,The maximum value of its bounds is unchanged,The minimum value is set to the value of the current node,That is, the node of the right subtree cannot be smaller than the value of the current node.

4. The judgment condition judges whether the scope of each node is in（min, max),Returns beyond this rangefalse,The constraints of the boundary conditions are given by the parameters passed during the recursion.

    

程序执行结果：

参考：小浩算法-BST及其验证