Repository navigation
Expand file tree
/
Copy pathFindWay.java
More file actions
106 lines (85 loc) · 2.05 KB
/
Copy pathFindWay.java
File metadata and controls
106 lines (85 loc) · 2.05 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.*;
class Solution {
public int[][] solution(int[][] nodeinfo) {
int len = nodeinfo.length;
BTree tree = new BTree();
int[][] input = new int[len][3];
for(int i=0; i<len; i++) {
input[i][0] = nodeinfo[i][0];
input[i][1] = nodeinfo[i][1];
input[i][2] = i+1;
}
Arrays.sort(input, new Comparator<int[]>() {
public int compare(int[] o1, int[]o2) {
return o2[1]-o1[1];
}
});
for(int i=0; i<len; i++) {
tree.insertBST(input[i][2], input[i][0]);
}
int[][] answer = new int[2][len];
tree.printPRE(answer[0]);
tree.printPOST(answer[1]);
return answer;
}
}
class BTree {
public TreeNode root;
public int printIdx = 0;
public TreeNode insertKey(TreeNode root, int label, int x) {
TreeNode p = root;
TreeNode newNode = new TreeNode(label, x);
if(p==null) return newNode;
else if(p.data>newNode.data) {
p.left = insertKey(p.left, label, x);
return p;
} else if(p.data<newNode.data) {
p.right = insertKey(p.right, label, x);
return p;
} else return p;
}
public void insertBST(int label, int x) {
root = insertKey(root, label, x);
}
public void preorder(TreeNode root, int[] ans) {
if(root!=null) {
ans[printIdx++] = root.label;
preorder(root.left, ans);
preorder(root.right, ans);
}
}
public void printPRE (int[] ans) {
printIdx = 0;
preorder(root, ans);
}
public void postorder(TreeNode start, int[] ans) {
if(start.left!=null) postorder(start.left, ans);
if(start.right!=null) postorder(start.right, ans);
ans[printIdx++] = start.label;
}
public void printPOST(int[] ans) {
printIdx = 0;
postorder(root, ans);
}
}
class TreeNode {
int label;
int data;
boolean printed;
TreeNode left, right;
public TreeNode() {
this.left = null;
this.right = null;
this.printed = false;
}
public TreeNode(int label, int data) {
this.label = label;
this.data = data;
this.left = null;
this.right = null;
this.printed = false;
}
public int getData() {
return data;
}
}