LeetCode #124: Binary Tree Maximum Path Sum

https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

Given a binary tree, the problem requires finding the maximum path sum. A path is a sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Algorithm:

1. Initialize a variable max_so_far to negative infinity.
2. Define a recursive function helper that takes in a node and returns the maximum path sum that can be obtained from that node to any leaf node.
3. If the current node is None, return 0.
4. Recursively calculate the maximum path sum for the left and right subtrees using the helper function.
5. Calculate the maximum sum that can be obtained from the current node to any leaf node, taking into account the left and right subtrees.
6. Update max_so_far to the maximum of its current value, the maximum sum from the current node to any leaf node, and the maximum sum that can be obtained by combining the left and right subtrees with the current node.
7. Return the maximum path sum that can be obtained from the current node to any leaf node.
8. Call the helper function on the root node to obtain the maximum path sum for the entire tree.
9. Return max_so_far.

Here is the solution in Python3:

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        max_so_far = float('-inf')
        def helper(root):
            nonlocal max_so_far
            if not root:
                return 0
            left_tree = helper(root.left)
            right_tree = helper(root.right)
            max_one = max(root.val, root.val+left_tree, root.val + right_tree)
            max_so_far = max(max_so_far, max_one, root.val+left_tree+right_tree)
            return max_one
        helper(root)
        return max_so_far

We start by initializing a variable max_so_far to negative infinity. We define a recursive function helper that takes in a node and returns the maximum path sum that can be obtained from that node to any leaf node. If the current node is None, we simply return 0. We then recursively calculate the maximum path sum for the left and right subtrees using the helper function. We calculate the maximum sum that can be obtained from the current node to any leaf node, taking into account the left and right subtrees. We update max_so_far to the maximum of its current value, the maximum sum from the current node to any leaf node, and the maximum sum that can be obtained by combining the left and right subtrees with the current node. Finally, we return the maximum path sum that can be obtained from the current node to any leaf node. We call the helper function on the root node to obtain the maximum path sum for the entire tree. Finally, we return max_so_far.

Time and Space Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the tree, since we visit each node only once. The space complexity of this solution is O(h), where h is the height of the tree, since the maximum space used by the recursion stack is h. Therefore, this solution is both time and space-efficient.