###### tags: `Leetcode` `hard` `tree` `python` `Top 100 Liked Questions`

# 124. Binary Tree Maximum Path Sum

## [題目連結:] https://leetcode.com/problems/binary-tree-maximum-path-sum/

## 題目:
A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence **at most once**. Note that the path does not need to pass through the root.

The **path sum** of a path is the sum of the node's values in the path.

Given the ```root``` of a binary tree, return the maximum **path sum** of any **non-empty** path.


#### [圖片來源:] https://leetcode.com/problems/binary-tree-maximum-path-sum/

## 解題想法:
* 此題要求最大值的path sum:
* 可由任一node開始，任一node結束(至少包含一個node)
* 不可重複使用node
* 不用一定要通過root
* node可能含負數
* Tree求路徑: 往遞歸思考
* 每一node期望求出，通過此點能得到最大值
* 設位於當前node時，node.val=x
* 遞歸求node.left 左子最大路徑值pathL
* 需比較pathL是否為負，若為負，則不採納，回傳0
* 遞歸求node.right 右子最大路徑值pathR
* 需比較pathR是否為負，若為負，則不採納，回傳0
* 該node為連接樞紐，連結左右路徑後的最大路徑值，與最終res進行比較更新
* res=max(res,root.val+pathL+pathR)
* **最終回傳的是**: root.val+max(pathL,pathR) 注意別搞混!
* 因為要回傳給上一層用，只能選擇一條路徑，不能走交岔路
* 示意圖

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        res=[]
        que=[root]
        while que:
            root=que.pop(0)
            res.append(root.val)
            if root.left:
                que.append(root.left)
            if root.right:
                que.append(root.right)
        print(res)
        
class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res=float('-inf')
        self.dfs(root)
        return self.res
    #經過該root能得到的最長路徑
    def dfs(self,root):
        if not root:
            return 0
        pathL=max(0, self.dfs(root.left))
        pathR=max(0, self.dfs(root.right))
        #更新self.res對決已該root為連接樞紐連接pathR+pathL的路徑
        self.res=max(self.res,root.val+pathL+pathR)
        return root.val+max(pathL,pathR)
    
if __name__=='__main__':
    root=TreeNode(-10)
    root.insertLeft(9)
    root.insertRight(20)
    root.right.insertLeft(15)
    root.right.insertRight(7)
    result=Solution()
    ans=result.maxPathSum(root)
    print(ans)