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