python：求二叉树的最大路径

Question

查阅了相关博主的资料，但运行出来的都是直接结束进程的。我想要验证数据该怎么搞。

Answer 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        
        def dfs(root):
            if not root:
                return float("-inf"), float("-inf")
            leftToRoot_max, leftNotToRoot_max = dfs(root.left)
            rightToRoot_max, rightNotToRoot_max = dfs(root.right)
            
            #最大根有关路径和
            toRoot_max = max(root.val, leftToRoot_max+root.val, rightToRoot_max+root.val)
            #最大根无关路径和
            notToRoot_max = max(leftToRoot_max+root.val+rightToRoot_max, leftNotToRoot_max, rightNotToRoot_max)
            # print(toRoot_max, notToRoot_max) 

            # 返回（最大根有关路径和， 最大路径和）
            return toRoot_max, max(notToRoot_max,toRoot_max)

        t, nt = dfs(root)
        return max(t,nt)