blob: 42583067f77131cd83468edbb25b2e2546d3454b (
plain)
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class TreeBstCheck {
static class FastScanner {
StringTokenizer tok = new StringTokenizer("");
BufferedReader in;
FastScanner() {
in = new BufferedReader(new InputStreamReader(System.in));
}
String next() throws IOException {
while (!tok.hasMoreElements())
tok = new StringTokenizer(in.readLine());
return tok.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
static class TreeOrders {
int n;
int[] key, left, right;
void read() throws IOException {
FastScanner in = new FastScanner();
n = in.nextInt();
key = new int[n];
left = new int[n];
right = new int[n];
for (int i = 0; i < n; i++) {
key[i] = in.nextInt();
left[i] = in.nextInt();
right[i] = in.nextInt();
}
}
boolean isBst() {
if (key.length == 0) return true;
Stack<Integer> keyIndexStack = new Stack<>();
ArrayList<Integer> result = new ArrayList<>();
boolean walkLeft = true;
int currentIndex = 0;
keyIndexStack.push(currentIndex);
while (!keyIndexStack.empty() || right[currentIndex] != -1) {
if (walkLeft) {
if (left[currentIndex] != -1) {
if (key[left[currentIndex]] >= key[currentIndex]) return false;
currentIndex = left[currentIndex];
keyIndexStack.push(currentIndex);
} else {
int i = keyIndexStack.pop();
if (result.size() > 0) {
if (key[i] < result.get(result.size()-1)) return false;
}
result.add(key[i]);
walkLeft = false;
}
} else {
if (right[currentIndex] != -1) {
if (key[right[currentIndex]] < key[currentIndex]) return false;
currentIndex = right[currentIndex];
keyIndexStack.push(currentIndex);
walkLeft = true;
} else {
if (!keyIndexStack.empty()) {
currentIndex = keyIndexStack.pop();
if (result.size() > 0) {
if (key[currentIndex] <= result.get(result.size()-1)) return false;
}
result.add(key[currentIndex]);
}
}
}
}
return true;
}
}
static public void main(String[] args) throws IOException {
TreeOrders tree = new TreeOrders();
tree.read();
if (tree.isBst()) {
System.out.println("CORRECT");
} else
System.out.println("INCORRECT");
}
}
|
