
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left =None
        self.right = None

# 只能從root開始的最大路徑和 (可以不選 都不選為0)
def maxPathSumRoot(root):
    if not root: return 0
    # 有選root 往左或往右
    left = maxPathSumRoot(root.left) + root.val
    right = maxPathSumRoot(root.right) + root.val
    # 沒選root
    result = 0
    return max(left, right, result)

import sys
class Solution:
    # 回傳任意起點走到任意終點的最大路徑和(不可以不選 只少選一個節點)
    def maxPathSum(self, root):
        if not root: return -(sys.maxsize)
        # 經過中間(root) 最大路徑和
        middle = maxPathSumRoot(root.left) + root.val + maxPathSumRoot(root.right)
        # 不經過中間的最大路徑和
        left = self.maxPathSum(root.left)
        right = self.maxPathSum(root.right)

        return max(left, right, middle)


if __name__=='__main__':
    root = TreeNode(-10)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    print(Solution().maxPathSum(root))
    

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left =None
        self.right = None

# 只能從root開始的最大路徑和 (可以不選 都不選為0)
def maxPathSumRoot(root):
    if not root: return 0
    # 有選root 往左或往右
    left = maxPathSumRoot(root.left) + root.val
    right = maxPathSumRoot(root.right) + root.val
    # 沒選root
    result = 0
    return max(left, right, result)

import sys
class Solution:
    # 回傳任意起點走到任意終點的最大路徑和(不可以不選 只少選一個節點)
    def maxPathSum(self, root):
        if not root: return -(sys.maxsize)
        # 經過中間(root) 最大路徑和
        middle = maxPathSumRoot(root.left) + root.val + maxPathSumRoot(root.right)
        # 不經過中間的最大路徑和
        left = self.maxPathSum(root.left)
        right = self.maxPathSum(root.right)

        return max(left, right, middle)


if __name__=='__main__':
    root = TreeNode(-10)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    print(Solution().maxPathSum(root))
    
# 只能從root開始的最大路徑和 (可以不選 都不選為0) # 有選root 往左或往右 # 沒選root # 回傳任意起點走到任意終點的最大路徑和(不可以不選 只少選一個節點) # 經過中間(root) 最大路徑和 # 不經過中間的最大路徑和