-
Notifications
You must be signed in to change notification settings - Fork 1.4k
/
Solution.java
70 lines (60 loc) · 1.83 KB
/
Solution.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
// github.com/RodneyShag
import java.util.Scanner;
// Main trick: Repesent our tree as a 1-D array
public class Solution {
public static void main(String[] args) {
/* Create tree */
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
Pair [] array = new Pair[N+1]; // represents our tree
for (int i = 1; i <= N; i++) {
array[i] = new Pair(scan.nextInt(), scan.nextInt());
}
/* Perform swaps and print inorder traversals */
int T = scan.nextInt();
while (T-- > 0) {
int K = scan.nextInt();
swap(array, K, N);
inorderTraverse(array, 1);
System.out.println();
}
scan.close();
}
private static void swap(Pair [] array, int K, int maxDepth) {
for (int h = K; h <= maxDepth; h += K) {
swap(array, h, 1, 1);
}
}
private static void swap(Pair [] array, int depthToSwap, int currIndex, int currDepth) {
if (currIndex < 1) {
return;
}
Pair p = array[currIndex];
if (currDepth == depthToSwap) {
p.swapSubtrees();
} else {
swap(array, depthToSwap, p.left, currDepth + 1);
swap(array, depthToSwap, p.right, currDepth + 1);
}
}
private static void inorderTraverse(Pair [] array, int index) {
if (index != -1) {
inorderTraverse(array, array[index].left);
System.out.print(index + " ");
inorderTraverse(array, array[index].right);
}
}
}
class Pair {
int left;
int right;
public Pair(int left, int right) {
this.left = left;
this.right = right;
}
public void swapSubtrees() {
int temp = left;
left = right;
right = temp;
}
}