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