友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
98. Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
-
The left subtree of a node contains only nodes with keys less than the node’s key.
-
The right subtree of a node contains only nodes with keys greater than the node’s key.
-
Both the left and right subtrees must also be binary search trees.
Example 1:
2 / \ 1 3 Input: [2,1,3] Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
思路分析
思路很简单，利用搜索二叉树的定义，界定好树的上下界，然后递归比较就好。
-
一刷
-
二刷
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;
}
}
直接使用“树形DP套路”+剪枝技巧，速度直接击败 100%。
这里有一点需要注意：最大值最小值用 Long.MIN_VALUE 和 Long.MAX_VALUE，这样可以防止单节点树 Integer.MAX_VALUE （最小值的单节点树应该也会有问题）造成的错误。
另外，查看了官方题解后，发现可以使用树的中序排列来检查（二叉搜索树中序排列是升序），这样跟前几天在牛客网上做的那个“发现二叉搜索树中的两个错误节点”的思路就一致了。回头尝试一下。
