aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--path_zigzag_labelled_bt.c52
-rw-r--r--path_zigzag_labelled_bt.py35
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))