blob: bbff1b5674a328522d2264c459db80f7017fe2d3 (
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
|
// 1104. Path In Zigzag Labelled Binary Tree
#include "leetcode.h"
/*
* in an infinite binary ree where every node has two children, the nodes are
* labelled in row order. in the odd numbered rows, the labelling is left to
* right, while in the even numbered rows, the labelling is right to left. given
* the 'label' of a node in this tree, return the labels in the path from the
* root of the tree to the node with that 'label'
*/
int find_row(int label) {
int row = 1;
while ((1 << row) <= label)
row++;
return row;
}
int find_label_idx(int label) {
int row = find_row(label);
if (!(row % 2))
return 3 * (1 << (row - 1)) - label - 1;
return label;
}
int find_label(int idx) { return find_label_idx(idx); }
int *pathInZigZagTree(int label, int *returnSize) {
int row = find_row(label);
*returnSize = row;
int *ans = (int *)malloc(row * sizeof(int));
ans[--row] = label;
int parent = find_label_idx(label);
while (parent != 1) {
parent /= 2;
ans[--row] = find_label(parent);
}
return ans;
}
int main() {
int rs1, rs2;
int *pizzt1 = pathInZigZagTree(14, &rs1);
int *pizzt2 = pathInZigZagTree(26, &rs2);
for (int i = 0; i < rs1; i++)
printf("%d ", pizzt1[i]); // expect: 1 3 4 14
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", pizzt2[i]); // expect: 1 2 6 10 26
printf("\n");
free(pizzt1), free(pizzt2);
}
|