98 BST及其验证

BST即二叉binary search tree，二叉搜索树，也有称为是二叉排序树的，当对其使用中序遍历的时候可以得到一个递增的序列。

 

题目描述

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

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

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

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

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

 

示例

输入：

2 / 1 3

输出：true

输入：

​ 5

/ \

1 4

​ / \

​ 3 6

输出：false

解释：根节点的值为5，但是其右子节点的值为4，不满足右子树所有节点的值大于根节点的条件

 

题目解析

   根据题目提示的深度优先搜索，可以使用递归的方式来写。每次判断左右子树是否满足二叉搜索树的条件即可；

左子树的所有节点的值小于根节点的值

右子树所有节点的值大于根节点的值

  但是这里并不仅仅只是比较根节点和左右节点的值满足条件即可，它是要在整棵二叉树上都满足条件的，因此对于每个节点的取值应该有一个边界范围，例如：

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

  因此在递归的时候返回false时就不能只是比较左右节点和父亲节点的大小了，具体怎么做也是看了大佬的代码之后才理解的，代码如下：

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); }

 

实现思路如下：

先使用一个极大值和极小值充当边界的判断条件，确保整颗树的根节点值在这个范围内，这里使用Long类型的最大值是因为自己在代码提交的时候有个测试用例是int类型的最大值，导致错误。

程序第一进入isBST函数时，对于

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

该条件的bool值为真。则进入到下面的递归条件中。

而这个递归也被设置的很简洁，对于左子树的节点，其边界的最小值没有改变，而最大值设置为当前节点的值，即左子树的节点不能比当前节点的值大；对于右子树的节点，其边界的最大值没有改变，而最小值设置为当前节点的值，即右子树的节点不能比当前节点的值小。

判断条件判断每个节点的范围是否在（min, max)，超出该范围则返回false，而边界条件的约束又由递归时候参数传递给出。

 

程序执行结果：

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