124，二叉樹中的最大路徑和

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
a.left = b
a.right = c

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        # 定義一個數字存放最大的路徑和
        self.max_sum = float("-inf")
        def dfs(root):
            # 當節點為空的時候返回零
            if not root:return 0
            # 遞歸左子樹和右子樹，並接收返回值
            left = dfs(root.left)
            right = dfs(root.right)
            # self.max_sum必然是left或者right的子樹的路徑，
            # 因此這裡判斷是否需要經過根節點
            self.max_sum = max(self.max_sum,left + right + root.val)
            # 這裡不針對根節點，對於根節點的兒子節點來說，
            # 路徑只能包含兒子節點中的一個
            return max(0,max(left,right) + root.val)
        dfs(root)
        return self.max_sum
A = Solution()
print(A.maxPathSum(a))