題目

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

本題中，路徑被定義為一條從樹中任意節點出發，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點。

示例 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]