数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python二叉树最大路径和
假设我们有一个非空的二叉树。我们需要找到路径和。这里，路径是从某个起始节点到任何节点的任何节点序列，其中存在父子连接。路径必须包含至少一个节点，并且不需要经过根节点。如果输入树为：
则输出将为32。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为solve()的方法，它将接收节点作为参数。
如果节点为空或节点的值为0，则返回0。
left := 0和solve(节点的左子节点)中的最大值
right := 0和solve(节点的右子节点)中的最大值
ans := ans和left + right + 节点数据中的最大值
返回节点数据 + left和right中的最大值
在主方法中，设置ans := -inf，然后调用solve(root)并返回ans。
示例
让我们看下面的实现来更好地理解：
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
class Solution(object):
def maxPathSum(self, root):
self.ans = -float('inf')
self.solve(root)
return self.ans
def solve(self,node):
if not node or node.data == 0:
return 0
left = max(0,self.solve(node.left))
right = max(0,self.solve(node.right))
self.ans = max(self.ans,left+right+node.data)
return node.data + max(left,right)
ob = Solution()
root = make_tree([-10,9,10,None,None,15,7])
print(ob.maxPathSum(root))输入
[-10,9,10,None,None,15,7]
输出
32
更新于：2020年5月26日
797 次浏览
广告