最初看这道题的时候,发现通过率36%,觉得比较神奇,按理说应该是相对简单的题目。结果啪啪打脸,长时间没有做树相关的题目,连这种基础题型都忘记怎么做了。好在经过两次错误尝试后,发现了正常解题方案。
验证二叉搜索树
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:root = [2,1,3]
输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1
解题思路
要解这道题,需要先明白二叉搜索树的定义和特性。
设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点,那么y.key≤x.key。如果y是x右子树中的一个结点,那么y.key≥x.key。
在二叉搜索树中:
1.若任意结点的左子树不空,则左子树上所有结点的值均不大于它的根结点的值。
2.若任意结点的右子树不空,则右子树上所有结点的值均不小于它的根结点的值。
3.任意结点的左、右子树也分别为二叉搜索树。
根据二叉搜索树的特性,我们能发现根节点左侧节点值必然比根节点小,右侧节点值必然比根节点大,所以如果以中序遍历树的话,值应该是单调递增的。
最开始都忘记什么叫二叉搜索树了,写最初版本方案的时候也没有考虑用中序遍历,一顿操作猛如虎,收获两次解答错误。
代码
1 | //中序遍历,判断是否递增 |
这个代码有一处优化点,可以提前判断要加入bstVal中的值,与其前一个值的大小是否符合规范,如果不符合,可尽早结束执行。
1 | var bstVal []int |