Python程式：查詢二叉樹中任意路徑的最大和

假設我們有一個二叉樹，我們需要找到從根節點到葉節點的任意路徑的最大和。

例如，輸入為：

則輸出為 29，因為從根節點出發，如果我們沿著 5->9->7->8 這條路徑，則相加結果為 29。

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

  • 定義一個函式 walk()。它將接收節點和 s 作為引數。

  • 如果節點為空，則：

    • max_sum := max_sum 和 s 的最大值

    • 返回

  • s := s + 節點的值

  • walk(節點的左子節點, s)

  • walk(節點的右子節點, s)

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

  • max_sum := 0

  • walk(根節點, 0)

  • 返回 max_sum

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

示例

線上演示

from collections import defaultdict
   class TreeNode:
      def __init__(self, data, left = None, right = None):
         self.data = data
         self.left = left
         self.right = right
   class Solution:
      def walk(self, node, s):
         if not node:
            self.max_sum = max(self.max_sum, s)
         return
      s += node.data
      self.walk(node.left, s)
      self.walk(node.right, s)
   def solve(self, root):
      self.max_sum = 0
      self.walk(root, 0)
   return self.max_sum
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

輸入

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

輸出

29

更新於：2020年10月5日

114 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告