forked from algorithmzuo/algorithm-primary
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCode05_IsBinarySearchTree.java
More file actions
85 lines (77 loc) · 2.07 KB
/
Code05_IsBinarySearchTree.java
File metadata and controls
85 lines (77 loc) · 2.07 KB
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
package class07;
public class Code05_IsBinarySearchTree {
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public static class Info {
public boolean isBST;
public int max;
public int min;
public Info(boolean is, int ma, int mi) {
isBST = is;
max = ma;
min = mi;
}
}
// public static Info process(TreeNode x) {
// if (x == null) {
// return null;
// }
// Info leftInfo = process(x.left);
// Info rightInfo = process(x.right);
// int max = x.val;
// int min = x.val;
// if (leftInfo != null) {
// max = Math.max(leftInfo.max, max);
// min = Math.min(leftInfo.min, min);
// }
// if (rightInfo != null) {
// max = Math.max(rightInfo.max, max);
// min = Math.min(rightInfo.min, min);
// }
// boolean isBST = true;
// if (leftInfo != null && !leftInfo.isBST) {
// isBST = false;
// }
// if (rightInfo != null && !rightInfo.isBST) {
// isBST = false;
// }
// boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
// boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
// if (!(leftMaxLessX && rightMinMoreX)) {
// isBST = false;
// }
// return new Info(isBST, max, min);
// }
public static Info process(TreeNode x) {
if (x == null) {
return null;
}
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
int max = x.val;
int min = x.val;
if (leftInfo != null) {
max = Math.max(leftInfo.max, max);
min = Math.min(leftInfo.min, min);
}
if (rightInfo != null) {
max = Math.max(rightInfo.max, max);
min = Math.min(rightInfo.min, min);
}
boolean isBST = false;
boolean leftIsBst = leftInfo == null ? true : leftInfo.isBST;
boolean rightIsBst = rightInfo == null ? true : rightInfo.isBST;
boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
if (leftIsBst && rightIsBst && leftMaxLessX && rightMinMoreX) {
isBST = true;
}
return new Info(isBST, max, min);
}
}