知一的指纹

98. 验证二叉搜索树

版权声明: 本文为博主原创文章,发表自 知一的指纹。转载需向 我的邮箱 申请。

题目

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

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

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

输入:

1
2
3
  2
/ \
1 3

输出: true
示例 2:

输入:

1
2
3
4
5
  5
/ \
1 4
  / \
  3 6

输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。

思路

首先拿到这个题看起来思路比较简单,实现起来还有有点困难,而且在思考过程中踩过一个坑,又爬上来的。哎,看题还是要全面点。

  1. 首先想到就是中序遍历了,放到一个列表中,然后比较大小即可。
  2. 或者是做一个递归操作,判断当前节点是否在一个范围即可。

思路是这么两个思路,代码实现起来为了执行效率做了短路处理,就是边遍历边检查,遇到错误就一路返回不再进行后面处理,当然这是思路理顺后的优化。

中序遍历没坑,直接写就行了,有坑的是第二种操作,刚开始觉得只要比较当前节点的父节点和两个子节点就好了,就像下面画的,已 C 点为当前节点进行处理,实际是一个错误的思路,并且情况也分析的不对。

意识到问题后就重新分析,把当前节点作为最底端的节点,我们去比较的都是当前节点和父辈及以上的节点的大小,也就是拆出来四种情况。

其中 表示当前节点,和其它点的相对位置表示左右子节点关系,min -> max 指向当前节点值必须在此区间中才可以,+∞-∞ 为单点情况的边界表示。最后拆分出这四种子情况,只要任一节点符合这四种情况之一即当前节点满足,当所有节点均满足则二叉搜索🌲有效,事实根据这个思路写出的代码验证是可行的。比较开心的是重新思考后的思路写出来的代码一次通过✌️。

代码

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root){
return forEachNode(root, new ArrayList<>());
}

public boolean forEachNode(TreeNode node, List<Integer> val){
if (null == node) {
return true;
}
if (!forEachNode(node.left, val)){
return false;
}
if (!validOrAdd(val, node)){
return false;
}
if (!forEachNode(node.right, val)){
return false;
}
return true;
}
public boolean validOrAdd(List<Integer> val, TreeNode node){
if(val.size() > 0 && val.get(val.size() - 1) >= node.val){
return false;
}else{
return val.add(node.val);
}
}
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root){
return subValidBSTLeft(root, null, null);
}

public boolean subValidBSTLeft(TreeNode node, Integer min, Integer max) {
if (null == node){
return true;
}
if (null == min && null == max){
}else if (null == min && null !=max && node.val < max){
}else if (null != min && null == max && min < node.val){
}else if (null != min && null != max && min < node.val && node.val < max){
}else {
return false;
}
// left
if (!subValidBSTLeft(node.left, min, node.val)){
return false;
}
// right
if (!subValidBSTLeft(node.right, node.val, max)){
return false;
}
return true;
}
}

如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!
Noogel's WeChat Pay

微信打赏

Noogel's Alipay

支付宝打赏