lc124. 二叉树中的最大路径和

分治法：
当前的最大值为 当前值、当前值+左孩子的值、 当前值+右孩子的值 的最大值。
保留的最大值为 当前值最大值、保留的最大值、 当前值++左孩子的值+右孩子的值 的最大值。

def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        self.res = float("-inf")
        self.dfs(root)
        return self.res
    
    def dfs(self, root):
        if not root:
            return 0
        left_res = self.dfs(root.left)
        right_res = self.dfs(root.right)
        cur = max(root.val, root.val + left_res, root.val + right_res)
        self.res = max(self.res, cur, root.val + left_res + right_res)
        return cur