-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.java
More file actions
65 lines (64 loc) · 1.84 KB
/
Copy pathSolution.java
File metadata and controls
65 lines (64 loc) · 1.84 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
import java.util.HashMap;
public class Solution {
public TreeNode createBinaryTree(String[] inputs) {
TreeNode result = null, cur;
HashMap<Integer, TreeNode> hash = new HashMap<>();
int size = inputs.length;
for (int idx = 0; idx < size; idx++) {
int num = 0;
String val = inputs[idx];
if (!val.equals("null")) {
num = Integer.parseInt(val);
}
if (idx == 0) {
result = new TreeNode(num);
hash.put(num, result);
}
if (hash.containsKey(num)) {
cur = hash.get(num);
} else {
cur = new TreeNode(num);
hash.put(num, cur);
}
if (2*idx+1 < size) {
if (!inputs[2*idx+1].equals("null")) {
int leftVal = Integer.parseInt(inputs[2*idx+1]);
if (hash.containsKey(leftVal)) {
cur.left = hash.get(leftVal);
} else {
cur.left = new TreeNode(leftVal);
hash.put(leftVal, cur.left);
}
}
}
if (2*idx+2 < size) {
if (!inputs[2*idx+2].equals("null")) {
int rightVal = Integer.parseInt(inputs[2*idx+2]);
if (hash.containsKey(rightVal)) {
cur.right = hash.get(rightVal);
} else {
cur.right = new TreeNode(rightVal);
hash.put(rightVal, cur.right);
}
}
}
}
return result;
}
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return checkBST(root, Double.MAX_VALUE, -Double.MAX_VALUE);
}
public boolean checkBST(TreeNode root, double upperbound, double lowerbound) {
if (root == null) {
return true;
}
double cur = (double)(root.val);
if (cur >= upperbound || cur <= lowerbound) {
return false;
}
return checkBST(root.left, cur, lowerbound) && checkBST(root.right, upperbound, cur);
}
}