Python程式：查詢二叉樹中每條對角線路徑元素的和

假設我們有一個二叉樹，我們需要找到從樹的頂部到右下角的每條對角線的元素之和。

因此，如果輸入如下所示：

則輸出將為 [27, 18, 3]，因為對角線為 [12,15]、[8,10]、[3]。所以和值為 [27, 18, 3]

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

定義一個函式 traverse()。它將接收節點、左側節點數、輸出作為引數。

  • 如果節點為空，則

    • 返回。

  • 如果左側節點數大於或等於輸出的大小，則

    • 將節點的資料插入到輸出的末尾。

  • 否則，

    • 輸出[左側節點數] := 輸出[左側節點數] + 節點的資料。

  • 如果節點的左子節點不為空，則

    • 遍歷(節點的左子節點, 左側節點數+1, 輸出)。

  • 如果節點的右子節點不為空，則

    • 遍歷(節點的右子節點, 左側節點數, 輸出)。

  • 在主方法中，執行以下操作：

  • 輸出 := 一個新的列表。

  • 遍歷(根節點, 0, 輸出)。

  • 返回輸出。

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

示例

 線上演示

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root):
      output = []
      def traverse(node, numLeft, output):
         if not node:
            return
         if numLeft >= len(output):
            output.append(node.data)
         else:
            output[numLeft] += node.data
         if node.left:
            traverse(node.left, numLeft+1, output)
         if node.right:
            traverse(node.right, numLeft, output)
      traverse(root, 0, output)
      return output
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root))

輸入

root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)

輸出

[27, 18, 3]

更新於: 2020年10月7日

109 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告