用 Python 编写程序，用于查找二叉树从根到叶的最长路径和之和

pythonserver side programmingprogramming更新于 2026/1/24 1:16:17

假设我们有一棵二叉树，我们必须找到从根到叶节点的最长路径和之和。如果有两条相同的长路径，则返回和较大的路径。

因此，如果输入如下

则输出为 20。

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

定义一个函数 rec() 。这将获取 curr
如果 curr 为空，则
- return(0, 0)
bigger := rec(curr 左侧) 的最大值，rec(curr 右侧)
返回一对 (bigger[0] + 1, greater[1] + curr 的值)
从主方法执行以下操作 −
ret := rec(root)
返回 ret 的第 1 个索引

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

示例

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)