題目

給定一個(gè)非空二叉樹，返回其最大路徑和。

本題中，路徑被定義為一條從樹中任意節(jié)點(diǎn)出發(fā)，達(dá)到任意節(jié)點(diǎn)的序列。該路徑至少包含一個(gè)節(jié)點(diǎn)，且不一定經(jīng)過根節(jié)點(diǎn)。

示例 1:

輸入: [1,2,3]

            
                 1
  / \
 2   3

            
          

輸出: 6
示例 2:

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

            
                -10
   / \
  9  20
    /  \
   15   7

            
          

輸出: 42

思路

關(guān)鍵是要求出，某一個(gè)根節(jié)點(diǎn)到某個(gè)子節(jié)點(diǎn)的最長路徑是多少。最后的結(jié)果一定是某一個(gè)根節(jié)點(diǎn)的值加上它左右子樹的那個(gè)最長路徑。
代碼如下，

代碼

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]
#某一個(gè)根節(jié)點(diǎn)到某個(gè)子節(jié)點(diǎn)的最長路徑
        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]