diff options
-rw-r--r-- | path_zigzag_labelled_bt.c | 52 | ||||
-rw-r--r-- | path_zigzag_labelled_bt.py | 35 |
2 files changed, 87 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); +} diff --git a/path_zigzag_labelled_bt.py b/path_zigzag_labelled_bt.py new file mode 100644 index 0000000..35f3928 --- /dev/null +++ b/path_zigzag_labelled_bt.py @@ -0,0 +1,35 @@ +# 1104. Path In Zigzag Labelled Binary Tree + +""" +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' +""" + + +class Solution(object): + def pathInZigZagTree(self, label): + """ + :type label: int + :rtype: List[int] + """ + ans = [] + node_cnt, level = 1, 1 + while label >= node_cnt * 2: + node_cnt *= 2 + level += 1 + while label != 0: + ans.append(label) + level_max = 2 ** (level) - 1 + level_min = 2 ** (level - 1) + label = int((level_max + level_min - label) / 2) + level -= 1 + return ans[::-1] + + +if __name__ == "__main__": + obj = Solution() + print(obj.pathInZigZagTree(14)) + print(obj.pathInZigZagTree(26)) |