题解 | #二叉树中的最大路径和#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型
# 树形DP
class Solution:
    def max_ans(self, root, max_num):
        if root == None:
            return 0
        if root.left == None and root.right == None:
            nowSum = root.val
            max_num = max(max_num, nowSum)
            print(max_num)
            return root.val, max_num
        else:
            if root.left != None:
                left, max_num = self.max_ans(root.left, max_num)
            else:
                left = 0
            if root.right != None:
                right, max_num = self.max_ans(root.right, max_num)
            else:
                right = 0
            nowSum = root.val
            if(left > 0): 
                nowSum += left
            if(right > 0): 
                nowSum += right
            max_num = max(max_num, nowSum, root.val, root.val + left, root.val + right)
            print(max_num)
            return max(root.val, root.val + left, root.val + right), max_num
        
        
    def maxPathSum(self , root: TreeNode) -> int:
        # write code here
        pre, sum_num = self.max_ans(root, -10000)
        return sum_num