leetcode_124. 二叉树中的最大路径和
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入:[1,2,3]
1 ...
目录
一、题目内容
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入:[1,2,3]
1
/ \
2 3输出:6
示例 2:
输入:[-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7输出:42
二、解题思路
后序遍历,计算左右子树的路径和,如果存在小于0的数则不算在路径内(加0),每次记录一下根左右三个点的路径和,然后返回父节点选择左子树或右子树的路径和,这样就可以记录子树选路径的情况。
三、代码
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def __repr__(self):
return str(self.val)
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
self.result = root.val
def dfs(root):
if not root:
return 0
left = max(dfs(root.left), 0) # less than 0, no pass
right = max(dfs(root.right), 0) # less than 0, no pass
self.result = max(root.val + left + right, self.result)
return root.val + max(left, right) # choose left or right
dfs(root)
return self.result
if __name__ == '__main__':
# a = TreeNode(-10)
# a.left = TreeNode(9)
# a.right = TreeNode(20)
# a.right.left = TreeNode(15)
# a.right.right = TreeNode(7)
a = TreeNode(1)
a.left = TreeNode(-2)
a.right = TreeNode(3)
s = Solution()
ans = s.maxPathSum(a)
print(ans)
文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。
原文链接:nickhuang1996.blog.csdn.net/article/details/108730702
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)