class Solution(object):
    def dfs(self, child, parent, root_object):
        self.max = max(self.max, child.val)
        if child.left != None:
            self.dfs(child.left, child, root_object)
        if child.right != None:
            self.dfs(child.right, child, root_object)
        if child.left == None and child.right == None:
            left_value = parent.left.val if parent.left != None else 0
            right_value = parent.right.val if parent.right != None else 0
            if child == parent.right or parent.right == None:
                if parent != root_object:
                    self.max = max(self.max, parent.val, parent.val + left_value, parent.val + right_value, parent.val + left_value + right_value)
                    parent.val = max(parent.val, parent.val + left_value, parent.val + right_value)
                    parent.left = None
                    parent.right = None
                else:
                    parent.val = max(parent.val, parent.val + left_value, parent.val + right_value, parent.val + left_value + right_value)
                    self.max = max(self.max, parent.val)

    def maxPathSum(self, root):
        self.max = root.val
        if root.left != None:
            self.dfs(root.left, root, root)
        if root.right != None:
            self.dfs(root.right, root, root)
        return self.max