友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
98. 验证二叉搜索树
给你一个二叉树的根节点 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
思路分析
思路很简单，利用搜索二叉树的定义，界定好树的上下界，然后递归比较就好。
直接使用“树形DP套路”+剪枝技巧，速度直接击败 100%。
这里有一点需要注意：最大值最小值用 Long.MIN_VALUE 和 Long.MAX_VALUE，这样可以防止单节点树 Integer.MAX_VALUE （最小值的单节点树应该也会有问题）造成的错误。
另外，查看了官方题解后，发现可以使用树的中序排列来检查（二叉搜索树中序排列是升序），这样跟前几天在牛客网上做的那个“发现二叉搜索树中的两个错误节点”的思路就一致了。回头尝试一下。
-
一刷
-
二刷
-
三刷
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
/**
* Runtime: 1 ms, faster than 33.82% of Java online submissions for Validate Binary Search Tree.
*
* Memory Usage: 45.2 MB, less than 5.58% of Java online submissions for Validate Binary Search Tree.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-24 19:06
*/
public boolean isValidBST(TreeNode root) {
if (Objects.isNull(root)) {
return true;
}
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode root, Integer lower, Integer upper) {
if (Objects.isNull(root)) {
return true;
}
int val = root.val;
if (Objects.nonNull(lower) && val <= lower) {
return false;
}
if (Objects.nonNull(upper) && upper <= val) {
return false;
}
if (!isValidBST(root.left, lower, val)) {
return false;
}
if (!isValidBST(root.right, val, upper)) {
return false;
}
return true;
}
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
38
39
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-23 16:38:11
*/
public boolean isValidBST(TreeNode root) {
return dfs(root).valid;
}
private Record dfs(TreeNode node) {
if (node == null) {
return new Record(true, Long.MIN_VALUE, Long.MAX_VALUE);
}
Record left = dfs(node.left);
if (!left.valid) {
return new Record(false, Long.MIN_VALUE, Long.MAX_VALUE);
}
Record right = dfs(node.right);
if (!right.valid) {
return new Record(false, Long.MIN_VALUE, Long.MAX_VALUE);
}
long max = Math.max(left.max, Math.max(node.val, right.max));
long min = Math.min(left.min, Math.min(node.val, right.min));
return new Record(left.valid && right.valid
&& left.max < node.val && node.val < right.min, max, min);
}
public static class Record {
public boolean valid;
public long max;
public long min;
public Record(boolean valid, long max, long min) {
this.valid = valid;
this.max = max;
this.min = min;
}
}
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
38
39
40
41
42
43
44
45
46
47
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-12 22:00:35
*/
public boolean isValidBST(TreeNode root) {
if (null == root) {
return true;
}
return dfs(root).valid;
}
private Record dfs(TreeNode root) {
if (Objects.isNull(root)) {
return null;
}
Record left = dfs(root.left);
if (Objects.nonNull(left) && (!left.valid || root.val <= left.max)) {
left.valid = false;
return left;
}
Record right = dfs(root.right);
if (Objects.nonNull(right) && (!right.valid || right.min <= root.val)) {
right.valid = false;
return right;
}
Record record = new Record();
record.min = Objects.isNull(left) ? root.val : left.min;
record.max = Objects.isNull(right) ? root.val : right.max;
record.valid = true;
return record;
}
private static class Record {
int min;
int max;
boolean valid;
public Record() {
}
public Record(int min, int max, boolean valid) {
this.min = min;
this.max = max;
this.valid = valid;
}
}