LeetCode 腾讯50题Python实现之《二叉树中的最大路径》

题目

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

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

示例 1:

输入: [1,2,3]

            
                 1
  / \
 2   3

            
          

输出: 6
示例 2:

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

            
                -10
   / \
  9  20
    /  \
   15   7

            
          

输出: 42

思路

关键是要求出，某一个根节点到某个子节点的最长路径是多少。最后的结果一定是某一个根节点的值加上它左右子树的那个最长路径。
代码如下，

代码

ref:https://leetcode-cn.com/problems/two-sum/solution/di-gui-zhan-sheng-98-python-by-578123043/

            
              class Solution(object):
    def maxPathSum(self, root):
        maxx = [-999999]
#某一个根节点到某个子节点的最长路径
        def maxsum(root):
            if root == None:
                return 0
            else:
                l = maxsum(root.left)
                r = maxsum(root.right) 
                result = max(root.val+max(l, r),0)
                maxx[0] =max(maxx[0] , root.val+l+r)
                return result
        maxsum(root)
        return maxx[0]