数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找二叉树中两节点之间路径的最大和
假设我们有一个二叉树，我们需要找到任意两个节点之间任何路径的最大和。
所以，如果输入像
那么输出将是 62，因为节点是 [12,13,14,16,7]。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 utils()。它将接收根节点作为参数
如果根节点为空，则
返回 0
l := utils(根节点的左子节点)
r := utils(根节点的右子节点)
max_single := (l 和 r 中的最大值 + 根节点的值) 和 根节点的值 的最大值
max_top := max_single 和 l + r + 根节点的值 的最大值
res := res 和 max_top 的最大值
返回 max_single
从主方法中执行以下操作：
如果根节点为空，则
返回 0
res := 无穷大
utils(根节点)
返回 res
让我们看看下面的实现以获得更好的理解：
示例
class TreeNode:
def __init__(self, value):
self.val = value
self.left = None
self.right = None
class Solution:
def solve(self, root):
if root is None:
return 0
self.res = float("-inf")
self.utils(root)
return self.res
def utils(self, root):
if root is None:
return 0
l = self.utils(root.left)
r = self.utils(root.right)
max_single = max(max(l, r) + root.val, root.val)
max_top = max(max_single, l + r + root.val)
self.res = max(self.res, max_top)
return max_single
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))输入
root = TreeNode(13) root.left = TreeNode(12) root.right = TreeNode(14) root.right.left = TreeNode(16) root.right.right = TreeNode(22) root.right.left.left = TreeNode(4) root.right.left.right = TreeNode(7)
输出
62
更新于: 2020年10月9日
181 次查看
广告