Python程序：查找二叉树中从根节点到叶节点的最长路径和

假设我们有一个二叉树，我们需要找到从根节点到叶节点的最长路径的和。如果存在两条长度相同的路径，则返回路径和更大的那条。

所以，如果输入如下所示：

则输出将为 20。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数 rec()。它将接收 curr

  • 如果 curr 为空，则

    • 返回 (0, 0)

  • bigger := rec(curr 的左子树) 和 rec(curr 的右子树) 中较大的那个

  • 返回一个对 (bigger[0] + 1, bigger[1] + curr 的值)

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

  • ret := rec(根节点)

  • 返回 ret 的第一个索引

让我们看看下面的实现，以便更好地理解：

示例

 实时演示

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      def rec(curr):
         if not curr:
            return (0, 0)
         bigger = max(rec(curr.left), rec(curr.right))
         return (bigger[0] + 1, bigger[1] + curr.val)
      return rec(root)[1]
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

输入

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)

输出

20

更新于： 2020年10月10日

144 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告