Leetcode 1194 Solution

This article provides solution to leetcode question 1194 (path-in-zigzag-labelled-binary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 1194" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree

Solution

class Solution:
    def depth(self, x):
        cnt = 0
        while x:
            x = x // 2
            cnt += 1
        return cnt



    def process(self, x):
        d = self.depth(x)



        if d % 2 == 0:
            y = 1



            while not (y <= x < y * 2):
                y *= 2



            return 3 * y - 1 - x
        else:
            return x



    def pathInZigZagTree(self, label: int) -> List[int]:
        pos = self.process(label)



        res = []



        while pos:
            res = [pos] + res
            pos = pos // 2



        for i in range(len(res)):
            res[i] = self.process(res[i])



        return res