Introduction

In this blog post, we will explore how to solve the LeetCode problem "124" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. Example 1: Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6. Example 2: Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42. Constraints: The number of nodes in the tree is in the range [1, 3 * 104]. -1000 <= Node.val <= 1000

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Recursion with Post-order Traversal: Use a recursive approach to traverse the binary tree in a post-order fashion (left, right, root). This ensures that the path sums of subtrees are calculated before the current node.
• Calculate Max Path Sum at Each Node: For each node, calculate the maximum path sum that includes the node. This involves considering the node's value, the maximum path sums from its left and right children (but only if they're positive, as negative sums would decrease the overall path sum), and the combination of the node's value with both left and right children.

• Update Global Maximum: Maintain a global variable to store the overall maximum path sum found so far. Update this global variable whenever a larger path sum is encountered during the traversal.

• Time & Space Complexity: O(N) time complexity, where N is the number of nodes in the tree, due to the single traversal. O(H) space complexity, where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H = N, and in the best case (balanced tree), H = log N.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root: TreeNode) -> int:
    max_sum = float('-inf')

    def max_gain_from_subtree(node):
        nonlocal max_sum
        if not node:
            return 0

        # Calculate max gain from left and right subtrees
        left_gain = max(max_gain_from_subtree(node.left), 0)
        right_gain = max(max_gain_from_subtree(node.right), 0)

        # Calculate the price to start a new path at the current node
        price_newpath = node.val + left_gain + right_gain

        # Update max_sum if the new path is better
        max_sum = max(max_sum, price_newpath)

        # For recursion :
        # return the max gain if continue the same path
        return node.val + max(left_gain, right_gain)

    max_gain_from_subtree(root)
    return max_sum