Python 中之之字形標記二叉樹路徑

假設在一個無限二叉樹中，每個節點都有兩個子節點，節點按行順序標記。現在在奇數行（第一行、第三行、第五行……），標記是從左到右的，在偶數行（第二行、第四行、第六行……），標記是從右到左的。所以樹將是這樣的：

所以我們給出了這棵樹中一個節點的標籤，我們需要找到從樹的根節點到該節點的路徑上的標籤。所以如果輸入是 label = 14，那麼輸出將是 [1,3,4,14]

為了解決這個問題，我們將遵循以下步驟：

  • 定義兩個陣列 tree 和 res，將 0 和 1 插入到 tree 陣列中，設定 odd := 1，current := 1 和 two := 2

  • 如果 label = 1，則返回一個包含單個元素 1 的列表。

  • 建立一個無限迴圈：

    • 如果 odd 不為零，則

      • max_val := current + two

      • temp := max_val

      • 當 temp > current 時

        • 將 temp 插入到 tree 中

        • 如果 temp = label，則退出迴圈

        • 將 temp 減 1

      • 如果 tree 的最後一個元素是 label，則退出迴圈

      • current := max_val

    • 否則

      • temp := two

      • 當 temp 不為零時

        • temp := 1，將 current 加 1，然後將 current 插入到 tree 中

        • 如果 current = label，則退出迴圈

      • 如果 tree 的最後一個元素是 label，則退出迴圈

    • temp := temp * 2

    • 如果 odd 不為零，則 odd := false，否則 odd := true

  • index := tree 的長度 – 1

  • 當 index 不為 0 時

    • 將 tree[index] 插入到 res 陣列中

    • index := index / 2

  • res := res 的反轉列表

  • 返回 res

示例（Python）

讓我們看看以下實現，以便更好地理解：

 即時演示

class Solution(object):
   def pathInZigZagTree(self, label):
      tree = []
      res = []
      tree.append(0)
      tree.append(1)
      odd = 1
      current = 1
      two = 2
      if label == 1:
         return [1]
      while True:
         if odd:
            max_val = current + two
            temp = max_val
            while temp>current:
               tree.append(temp)
               if temp == label:
                  break
               temp-=1
            if tree[-1]== label:
               break
            current = max_val
         else:
            temp = two
            while temp:
               temp-=1
               current+=1
               tree.append(current)
            if current == label:
               break
            if tree[-1]== label:
               break
         two*=2
         odd = not odd
      index = len(tree)-1
      while index:
         res.append(tree[index])
         index//=2
      res=res[::-1]
      return res
ob = Solution()
print(ob.pathInZigZagTree(14))

輸入

14

輸出

[1,3,4,14]

更新於： 2020-04-30

151 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始
廣告