leetcode 124：二叉树中的最大路径和(python)

待我称王封你为后i 2023-10-11 09:53 53阅读 0赞

# 题目 #

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: \[1,2,3\]

1
          / \
         2   3
         2+1+3=6

输出: 6  
示例 2:

输入: \[-10,9,20,null,null,15,7\]

-10
       / \
      9  20
        /  \
       15   7
    15+20+7=42

输出: 42

来源：力扣（LeetCode）  
链接：[LeetCode124. 二叉树中的最大路径和][LeetCode124.]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 解法一 (递归法) #

*  思路  
    递归寻找能够构成最大路径的路径和。其中，  
    max1指可以继续往路径中添加节点的最大路径和  
    max2指不能再添加节点的最大路径和  
    （如例子2中，对“20”节点来说，max1=20+15=35，max2=15+20+7=42）
 *  代码

# Definition for a binary tree node.
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    
    class Solution:
        def maxPathSum(self, root: TreeNode) -> int:
            [max1,max2]=self.findmaxPath(root)
            return max(max1,max2)
        def findmaxPath(self,root):
            if root.left==None and root.right==None:
                return [root.val]*2
            l1=r1=0
            l2=r2=-10000
            if root.left:
                [l1,l2]=self.findmaxPath(root.left)
            if root.right:
                [r1,r2]=self.findmaxPath(root.right)
            max1=max(l1,r1,0)+root.val
            max2=max(l2,r2,l1+r1+root.val,max1)
            return [max1,max2]

*  结果  
    ![在这里插入图片描述][2019092220595967.png]

# 解法二(法一改进) #

*  思路  
    将法一中的max2设为全局变量，减少了值的传递
 *  代码

# Definition for a binary tree node.
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    
    class Solution:
        def __init__(self):
            self.imax=-10000
        def maxPathSum(self, root: TreeNode) -> int:
            self.findmaxPath(root)
            return self.imax
        def findmaxPath(self,root):
            if root==None:
                return 0
            lmax=max(self.findmaxPath(root.left),0)
            rmax=max(self.findmaxPath(root.right),0)
            self.imax=max(self.imax,lmax+rmax+root.val)
            return max(lmax,rmax)+root.val

*  结果  
    ![在这里插入图片描述][20190922212705535.png]

[LeetCode124.]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
[2019092220595967.png]: https://img-blog.csdnimg.cn/2019092220595967.png
[20190922212705535.png]: https://img-blog.csdnimg.cn/20190922212705535.png