-
Notifications
You must be signed in to change notification settings - Fork 94
/
ValidateBST.java
105 lines (95 loc) · 2.4 KB
/
ValidateBST.java
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package chapter04TreesAndGraphs;
/**
*
* Problem: Implement a function to check if a binary tree is a binary search
* tree.
*
* Solution: The first leverages the in-order traversal, and the second builds
* off the property that left <= current < right
*
* Time Complexity: O(N)
*
* Space Complexity: O(H). H is the height of the tree.
*
*/
public class ValidateBST {
/**
* method 1: Assume that the tree cannot have duplicate values. In-Order
* Traversal
*/
class WrapInt {
public int val;
public WrapInt(int val) {
this.val = val;
}
}
WrapInt last_printed = null;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// check left
if (!isValidBST(root.left)) {
return false;
}
// check current
if ((last_printed != null) && last_printed.val >= root.val) {
return false;
}
last_printed = new WrapInt(root.val);
// check right
if (!isValidBST(root.right)) {
return false;
}
return true;
}
/**
* method 2: left <= current < right; The Min / Max Solution
*/
public boolean isValidBST2(TreeNode root) {
return check(root, null, null);
}
public boolean check(TreeNode root, Integer min, Integer max) {
if (root == null) {
return true;
}
// When we branch right, min gets updated.
// When we branch left, max gets updated.
if ((min != null && root.val <= min) || (max != null && root.val > max)) {
return false;
}
if (!check(root.left, min, root.val) || !check(root.right, root.val, max)) {
return false;
}
return true;
}
// method 2.5: left <= current < right; The Min / Max Solution
class ResultType {
int max;
int min;
boolean is_bst;
public ResultType(int max, int min, boolean is_bst) {
this.max = max;
this.min = min;
this.is_bst = is_bst;
}
}
public boolean isValidBST25(TreeNode root) {
ResultType res = helper(root);
return res.is_bst;
}
private ResultType helper(TreeNode root) {
if (root == null) {
return new ResultType(Integer.MIN_VALUE, Integer.MAX_VALUE, true);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);
if (!left.is_bst || !right.is_bst) {
return new ResultType(0, 0, false);
}
if (root.left != null && left.max > root.val || root.right != null && right.min <= root.val) {
return new ResultType(0, 0, false);
}
return new ResultType(Math.max(root.val, right.max), Math.min(root.val, left.min), true);
}
}