资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/leetcode-124-Binary Tree Maximum Path Sum

leetcode-124-Binary Tree Maximum Path Sum

z2xy / 3372人阅读

摘要：题目描述举例题目分析找从任意节点出发的任意路径的最大长度。每个都有可能是其他路径上的，这种情况要，。每个都有可能作为中心，此时要左侧之前的路径最长长度，左侧之前的路径最长长度，此为中心时候的长度将这个分析单元递归封装，即可实现目标。

</>复制代码 
  1. 题目描述：
  2. </>复制代码 
    1. Given a binary tree, find the maximum path sum.
    2. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child
  3. connections. The path must contain at least one node and does not need
    to go through the root.
  4. 举例：
  5. </>复制代码 
    1. Given the below binary tree,
    2.    1
    3.   / 
    4.  2   3
    5. Return 6.
</>复制代码 
  1. 题目分析： 找从任意节点出发的任意路径的最大长度。  每个node都有可能是其他路径上的node，这种情况要max(left，right)。如此循环。  每个node都有可能作为中心node，此时要max(左侧之前的路径最长长度，左侧之前的路径最长长度，此node为中心时候的长度)
  2. 将这个分析单元递归封装，即可实现目标。
  3. # Definition for a binary tree node.
  4. class TreeNode:
  5.     def __init__(self, x):
  6.         self.val = x
  7.         self.left = None
  8.         self.right = None
  9. class Solution:
  10.     def dfs(self,node):
  11.         ls = rs = None
  12.         lmv = rmv = 0
  13.         if node.left:
  14.             lmv,ls=self.dfs(node.left)
  15.             lmv=max(lmv,0)
  16.         if node.right:
  17.             rmv,rs=self.dfs(node.right)
  18.             rmv=max(rmv,0)
  19.         # print(lmv,rmv,ls,rs)
  20.         mv=node.val+max(lmv,rmv)
  21.         sv=node.val+lmv+rmv
  22.         # mv=node.val
  23.         trans_list=[elem for elem in [sv,ls,rs] if elem]
  24.         if not trans_list:
  25.             trans_list=[0]
  26.         return mv,max(trans_list)
  27.     def maxPathSum(self, root):
  28.         """
  29.         :type root: TreeNode
  30.         :rtype: int
  31.         """
  32.         if not root:
  33.             return
  34.         mv,smv=self.dfs(root)
  35.         return max(mv,smv)
  36. if __name__=="__main__":
  37.     tn=TreeNode(2)
  38.     tn1=TreeNode(-1)
  39.     tn2=TreeNode(-2)
  40.     tn.left=tn1
  41.     tn.right=tn2
云服务器 GPU云服务器 Maximum sum hibernate 分页 sum three-sum

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41490.html

相关文章

  • LeetCode[124] Binary Tree Maximum Path Sum

    摘要：复杂度思路对于每一节点，考虑到这一个节点为止，所能形成的最大值。，是经过这个节点为止的能形成的最大值的一条支路。 Leetcode[124] Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. For this problem, a path is defined as any se...

    warmcheng 评论0 收藏0

  • leetcode124. Binary Tree Maximum Path Sum

    摘要：题目要求题目要求从二叉树中找到任意两个节点构成的一条路径，该路径上节点的和为最大。其实在这里我们通过递归的方法可以发现以下几种场景当前节点作为起始节点当前节点不是起始节点首先我们以当前节点作为根节点，找到可能构成的最大路径值。 题目要求 Given a binary tree, find the maximum path sum. For this problem, a path i...

    frank_fun 评论0 收藏0

  • [LeetCode] 124. Binary Tree Maximum Path Sum

    Problem Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child co...

    mdluo 评论0 收藏0

  • [Leetcode-Tree]Binary Tree Maximum Path Sum

    摘要：但是本题的难点在于，使用递归实现，但是前面的第四种情况不能作为递归函数的返回值，所以我们需要定义两个值，代表单边路径的最大值，用于递归用于和回路的较大值。 Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. For this problem, a path is defined as a...

    caige 评论0 收藏0

  • [Leetcode] Binary Tree Maximum Path Sum 二叉树最大路径和

    摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。代码连接父节点的最大路径是一二四这三种情况的最大值当前节点的最大路径是一二三四这四种情况的最大值用当前最大来更新全局最大 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum...

    魏宪会 评论0 收藏0

发表评论

登陆后可评论

0条评论

z2xy

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<