首页 > 试题广场 >

二叉树中的最大路径和

[编程题]二叉树中的最大路径和
  • 热度指数：77451 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。
注意:
1.同一个节点在一条二叉树路径里中最多出现一次
2.一条路径至少包含一个节点，且不一定经过根节点

给定一个二叉树的根节点root，请你计算它的最大路径和

例如：
给出以下的二叉树，

最优路径是:2=>1=>3，或者3=>1=>2，最大路径和=2+1+3=6

数据范围：节点数满足 1 \le n \le 10^5 ，节点上的值满足
要求：空间复杂度 ，时间复杂度
示例1

输入

{1,2,3}

输出

6
示例2

输入

{-20,8,20,#,#,15,6}

输出

41

说明


其中一条最大路径为:15=>20=>6，路径和为15+20+6=41
示例3

输入

{-2,#,-3}

输出

-2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Python 3
昊天明月头像 昊天明月
python  这个题解过不了。。。
class Solution:
    def __init__(self):
        self.maxSum = float("-inf")
       
    def maxPathSum(self , root ):
        # write code here
        def maxGain(node):
            if not node:
                return 0
            # 递归计算左右子节点的最大贡献值
            # 只有在最大贡献值大于 0 时，才会选取对应子节点
            leftGain = max(maxGain(node.left), 0)
            rightGain = max(maxGain(node.right), 0)
           
            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            priceNewpath = node.val + leftGain + rightGain
           
            # 更新答案
            self.maxSum = max(self.maxSum, priceNewpath)
       
            # 返回节点的最大贡献值
            return node.val + max(leftGain, rightGain)
        maxGain(root)
        return self.maxSum

发表于 2023-04-28 15:33:09 回复(0)
Python 3
牛的翼比头像 牛的翼比 
class Solution:
    def __init__(self):
        self.max_weight = -10000

    def maxPathSum(self, root: TreeNode) -> int:
        # write code here
        self.maxPath(root)
        return self.max_weight

    def maxPath(self, root):
        if root is None:
            return 0
        left_weight = self.maxPath(root.left)
        right_weight = self.maxPath(root.right)
        self.max_weight = max(
            self.max_weight,
            root.val + left_weight + right_weight,
            root.val,
            root.val + left_weight,
            root.val + right_weight,
        )
        ret = max(root.val, root.val + left_weight, root.val + right_weight)
        return ret
朋友们救救孩子，为什么这段代码自测一点问题也没有，提交死活提交不上去。显示如下：
程序异常退出，请检查是否存在语法错误或者数组越界非法访问等情况
File "/tmp/a.py3", line 14, in run
ret = solution.maxPathSum( root )
File "/tmp/solution.py", line 19, in maxPathSum
self.maxPath(root)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 26, in maxPath
right_weight = self.maxPath(root.right)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
File "/tmp/solution.py", line 26, in maxPath
right_weight = self.maxPath(root.right)
File "/tmp/solution.py", line 25, in maxPath
left_weight = self.maxPath(root.left)
.........


发表于 2022-03-09 16:11:11 回复(2)
Python 3
Joy_9头像 Joy_9 
class Solution:
    def maxPathSum(self , root: TreeNode) -> int:
        # write code here
        self.max_v=float('-inf')
        def sumpath(root):
            if not root:
                return 0
            left=sumpath(root.left)
            right=sumpath(root.right)
            self.max_v=max(self.max_v,root.val+left+right)
            return max(0,root.val+max(left,right))
        sumpath(root)
        return self.max_v

发表于 2022-01-25 05:03:09 回复(0)
Python 3
Offer.Request头像 Offer.Request
class Solution:
    ans = float("-inf")
    def maxPathSum(self , root ):
        # write code here
        self.traverse(root)
        return self.ans

    def traverse(self, root):
        if not root:
            return 0

        left = max(0, self.traverse(root.left))  # 节点值可能为负数，为负就不使用
        right = max(0, self.traverse(root.right))

        self.ans = max(self.ans, left+right+root.val)  # 获取当前节点连接左右子树后的路径长度
        cur = max(left+root.val, right+root.val)  # 获取当前节点作为子节点时存在的最大路径和
        return cur
发表于 2021-10-17 17:33:56 回复(0)
Python 3
VincentLau~头像 VincentLau~ 
class Solution:
    def maxPathSum(self , root ):
        # write code here
        self.res = -float("inf")
        def dfs(node):
            if not node: return -float("inf")
            l, r = dfs(node.left), dfs(node.right)
            tmp = max(l + node.val, r+node.val, node.val)
            self.res = max(self.res, tmp, l+r+node.val)
            return tmp
        dfs(root)
        return self.res

发表于 2021-07-26 23:53:48 回复(0)
提交观点

问题信息

树 dfs
难度：
5条回答 28944浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树中的最大路径和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号