NC6 二叉树中的最大路径和（Python 3）

dfs方法

class Solution:
    def maxPathSum(self , root: TreeNode) -> int:
        sum=float('-inf')
        def dfs(root):
            nonlocal sum
            if not root:
                return float('-inf')
            leftsum=dfs(root.left)
            rightsum=dfs(root.right)
            #可能成为新的最大路径的情况有：当前路径保持不变，这个节点+它的右子树，这个节点+它的左子树，这个节点+它的左右子树，这个节点本身
            sum=max(sum,leftsum+root.val,rightsum+root.val,rightsum+leftsum+root.val,root.val)
            #可以作为子路径的情况有：该节点自身，该节点+它的左子树最大路径，该节点+它的右子树最大路径（子路径不能是左中右）
            return max(root.val,root.val+leftsum,root.val+rightsum)
        dfs(root)
        return sum