求二叉树的最大路径和的算法思路

求二叉树的最大路径和，可以采用递归的思路进行求解。具体思路如下：

1. 定义一个全局变量maxSum，用于记录最大路径和。
2. 定义一个递归函数helper(node)来求解以当前节点为起点的最大路径和。
3. 在helper(node)中，首先判断当前节点是否为空，如果为空则返回0。
4. 然后递归求解当前节点左子树的最大路径和leftSum和右子树的最大路径和rightSum。
5. 接着，计算以当前节点为起点的最大路径和curSum。如果leftSum和rightSum都小于0，则curSum=node.val；否则curSum=node.val+max(leftSum,rightSum)。
6. 比较curSum和maxSum，将较大者赋值给maxSum。
7. 最后，helper(node)返回curSum。

最终的最大路径和为maxSum。

代码实现如下：

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.maxSum = float('-inf')
        
        def helper(node):
            if not node:
                return 0
            
            leftSum = max(0, helper(node.left))
            rightSum = max(0, helper(node.right))
            
            curSum = node.val + leftSum + rightSum
            self.maxSum = max(self.maxSum, curSum)
            
            return node.val + max(leftSum, rightSum)
        
        helper(root)
        
        return self.maxSum