diff options
Diffstat (limited to 'path_zigzag_labelled_bt.c')
-rw-r--r-- | path_zigzag_labelled_bt.c | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/path_zigzag_labelled_bt.c b/path_zigzag_labelled_bt.c new file mode 100644 index 0000000..bbff1b5 --- /dev/null +++ b/path_zigzag_labelled_bt.c @@ -0,0 +1,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); +} |