05 August 2008
在每个节点都有两个子节点的无限二叉树中，节点按行顺序标记。
在奇数行（即第一、第三、第五……）中，标签从左到右，而在偶数行（第二、第四、第六……）中，标签从右到右向左。
给定这棵树中节点的标签，返回从树根到具有该标签的节点的路径中的标签。
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
class Solution {
public List<Integer> pathInZigZagTree(int label) {
List<Integer> results = new ArrayList();
//find which row
int k = 1;
int v = (int) (Math.pow(2, k));
while (v <= label) {
k++;
v = (int) Math.pow(2, k);
}
int row = k;
results.add(label);
int prevV = label;
while (k > 1) {
int prevNodePos = 0;
if (row % 2 == 1) { //odd -> l to r
prevNodePos = 1 + (prevV - (int) (Math.pow(2, k - 1))) / 2;
prevV = 2 * (int) (Math.pow(2, k - 2)) - prevNodePos;
} else {
prevNodePos = (int) (Math.pow(2, k - 1)) / 2 - (prevV - (int) (Math.pow(2, k - 1))) / 2;
prevV = (int) (Math.pow(2, k - 2)) + prevNodePos - 1;
}
results.add(prevV);
k--;
}
reverse(results);
return results;
}
public void reverse(List<Integer> arr) {
int i = 0;
int j = arr.size() - 1;
while (i < j) {
int t = arr.get(j);
arr.set(j, arr.get(i));
arr.set(i, t);
i++;
j--;
}
}
}
The basic idea is to get the height of the node in the tree and then traverse back to root which is the tricky part (since it is zigzaged).
We know that the target node’s actual parent should be the parent of its symmetric node at current height. So we first get the current height which is the first for loop. Then, to get the symmetric node, we first need to realize the fact: (label of current node + label of symmetric node) == (label of minimum node at current height) + (label of maximum node at current height) The minimum label can be calculated by 2^(level - 1) and maximum label can be calculated by 2^(level) - 1, where level is the current height.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public List<Integer> pathInZigZagTree(int label) {
int size = 1;
int level = 1;
LinkedList<Integer> res = new LinkedList<>();
while ((size << 1) <= label) {
size <<= 1;
level++;
}
while (label != 0) {
res.addFirst(label);
label = ((1 << level) - 1 + (1 << (level - 1)) - label) / 2;
level--;
}
return res;
}
}