面试热题（验证二叉搜索树）

ゞ浴缸里的玫瑰 2023-10-14 18:59 12阅读 0赞

> 给你一个二叉树的根节点 `root` ，判断其是否是一个有效的二叉搜索树。
> 
> **有效** 二叉搜索树定义如下：
> 
>  *  节点的左子树只包含 **小于** 当前节点的数。
>  *  节点的右子树只包含 **大于** 当前节点的数。
>  *  所有左子树和右子树自身必须也是二叉树
> 
> ![011effcb6a4deb1ade49b7b1fb76f322.jpeg][]

二叉树满足以上3个条件，有些同学就会说，BST不就是左大右小么？我直接判断**root.val>root.left.val** 和**root.val<root.right.val**不就可以了么？

![527d532d5f7241ffbd59b1b4433bd2cb.png][]

这样肯定是不对的，因为BST左小右大的特性是指root.val要比左子树的所有节点要大，要比右子树上的所有节点要小，所以只是检查两个节点当前是不够的，我们可以通过辅助函数，增加函数参数列表，在参数中携带额外信息，将下一个节点的合理取值范围传递下去，进行判断

因为root节点开始没有范围的限制，所以我们对其的边界可以最小的无穷，最大也是无穷

isValidBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);

如果当前节点不符合合法边界，直接返回false

if(node.val<=lower||node.val>=upper){
                return false;
            }

去遍历当前节点的左子树和右子数，并更新取值范围

isValidBST(node.left,lower,node.val)&&isValidBST(node.right,node.val,upper);

![fe97976d12654d9dac55d3bad13b2dc1.png][]

结果：

![524dae5fe8a34fafa3f9d016ed7486c2.png][]

看到测试案例顿时豁然开朗，一看这种比较大的数，一看就是数值类型的问题，超出范围了，然后我们将Integer改为更大的Long,然后：

![a4e19aa3517a4e3781eab4875bb82dce.png][]

[011effcb6a4deb1ade49b7b1fb76f322.jpeg]: https://img-blog.csdnimg.cn/img_convert/011effcb6a4deb1ade49b7b1fb76f322.jpeg
[527d532d5f7241ffbd59b1b4433bd2cb.png]: https://img-blog.csdnimg.cn/527d532d5f7241ffbd59b1b4433bd2cb.png
[fe97976d12654d9dac55d3bad13b2dc1.png]: https://img-blog.csdnimg.cn/fe97976d12654d9dac55d3bad13b2dc1.png
[524dae5fe8a34fafa3f9d016ed7486c2.png]: https://img-blog.csdnimg.cn/524dae5fe8a34fafa3f9d016ed7486c2.png
[a4e19aa3517a4e3781eab4875bb82dce.png]: https://img-blog.csdnimg.cn/a4e19aa3517a4e3781eab4875bb82dce.png