leetcode 1104. Path In Zigzag Labelled Binary Tree(python)

語言: CN / TW / HK

本文已參與「掘力星計劃」,贏取創作大禮包,挑戰創作激勵金。

描述

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,...), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,...), 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.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

Note:

1 <= label <= 10^6

解析

根據題意,給出了一個無限滿二叉樹,所有的節點都被從 1 開始的整數打了標籤,而且在樹的奇數行都是正常的從左到右排列數字,但在樹的偶數行都是從右到左的順序排列數字,現在題目給出了一個目標數字 label ,讓我們在這棵樹中找出從根節點 root 到 label 的節點列表。

其實這道題就是一個找規律的題,只是套在了樹結構上。如果題中的樹是一棵節點數字正常的從左到右的樹,那麼可以看出來知道目標節點 label 之後,倒推其父節點都是 label// 2 ,一直到根節點 1 為止,假如目標 label 為 7 ,則結果為 [1,3,7] , 樹結構如下:

    1
    2       3
  4   5   6   7

但是現在的樹在偶數行上是反轉排列的,樹結構如下所示:

    1
    3       2
  4   5   6   7

所以我們只要知道從 label 到 root 經過的節點上,原來的位置上的數字是什麼就可以解決此題,通過找規律我們發現目標不管在偶數行還是奇數行,某個標籤 label 的原位置上的數字為

2 ** (level) - 1 + 2 ** (level-1) - label

level 為當前節點的深度,label 為當前節點的值,算出來即為當前位置的原值,對其除 2 取整數即可知道其父節點值為多少。不斷重複這個找當前位置的原值、以及除 2 取整數得到父節點的操作,直到層數到達第一層為之,然後將找到的所有的節點升序排列放入列表 result 中返回即可。

解答

class Solution(object):
    def pathInZigZagTree(self, label):
        """
        :type label: int
        :rtype: List[int]
        """
        result = [label]
        level = int(math.log(label, 2)) + 1
        while level>1:
            origin = 2 ** (level) - 1 + 2 ** (level-1) - label
            label = origin // 2
            result.append(label)
            level -= 1
        result = result[::-1]
        return result

執行結果

Runtime: 12 ms, faster than 92.11% of Python online submissions for Path In Zigzag Labelled Binary Tree.
Memory Usage: 13.4 MB, less than 63.16% of Python online submissions for Path In Zigzag Labelled Binary Tree.

解析

這種方法是在論壇裡面看的一種方法,我們的結果其實就是可以看作從 label 到根節點 root 的過程,如題中的目標 label 為 14 可以看成二進位制 1110 ,其在樹上的父節點為 4(100) ,4 的父節點為 3(11),3 的父節點為 1(1)可以發現規律就是父節點的值的二進位制和當前節點的二進位制存在關係:

parent = 1 + inverted(label[1:-1])

inverted 為函式,將 1 變為 0 ,將 0 變為 1 。一直重複這個計算過程,根據這個規律便可以解題。

解答

class Solution(object):
    def pathInZigZagTree(self, label):
        """
        :type label: int
        :rtype: List[int]
        """
        res = []
        while label != 1:
            res.append(label)
            label = int('1' + "".join(map(lambda x: '1' if x == '0' else '0', format(label, 'b')[1:-1])), 2)
        res.append(1)
        return reversed(res)

執行結果

Runtime: 37 ms, faster than 21.05% of Python online submissions for Path In Zigzag Labelled Binary Tree.
Memory Usage: 13.3 MB, less than 63.16% of Python online submissions for Path In Zigzag Labelled Binary Tree.

原題連結:https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/

您的支援是我最大的動力