aboutsummaryrefslogtreecommitdiff
path: root/path_zigzag_labelled_bt.py
diff options
context:
space:
mode:
Diffstat (limited to 'path_zigzag_labelled_bt.py')
-rw-r--r--path_zigzag_labelled_bt.py35
1 files changed, 35 insertions, 0 deletions
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))