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 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告