Simple Python solution O(n)

  • 0
    class Solution(object):
        def maxPathSum(self, root):
            def maxPathSumHelper(tree):
                if not tree:
                    return (0, 0)
                pathSumWithRootLeft, pathSumLeft = maxPathSumHelper(tree.left)
                pathSumWithRootRight, pathSumRight = maxPathSumHelper(tree.right)
                pathSumWithRoot = max([pathSumWithRootLeft+tree.val, pathSumWithRootRight+tree.val, tree.val])
                pathSum = max([pathSumLeft if tree.left else float('-inf'), pathSumRight if tree.right else float('-inf'),                     pathSumWithRoot, pathSumWithRootLeft+pathSumWithRootRight+tree.val])
                return (pathSumWithRoot, pathSum)
            return maxPathSumHelper(root)[1]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.