Day 25:Binary Tree Maximum Path Sum : Binary Search - leetcode - Python3

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

  

SOLUTION

# Definition for a binary tree node.

# class TreeNode:

#     def __init__(self, val=0, left=None, right=None):

#         self.val = val

#         self.left = left

#         self.right = right

class Solution:

    def maxPathSum(self, root: Optional[TreeNode]) -> int:

        result: List[int] = [root.val]

        def dfs(root): # depth first search

            if not root:

                return 0

            maxLeft = dfs(root.left)

            maxRight = dfs(root.right)

            maxLeft = max(maxLeft, 0)

            maxRight = max(maxRight, 0)

            result[0] = max(result[0], root.val + maxLeft + maxRight)

            return root.val  + max(maxLeft, maxRight)

        dfs(root)

        return result[0]

Time Complexity: O(n)

Space Complexity:O(n)

How it works:

1. The maxPathSum method takes a root node of a binary tree as input and returns an integer, which represents the maximum path sum.

2. Inside the maxPathSum method, a variable result is initialized as a list with a single element, which is the value of the root node. This list is used to keep track of the maximum path sum throughout the recursion.

3. The code defines a nested function dfs (depth first search) that performs a recursive depth-first traversal of the binary tree.

4. The dfs function takes a root node as input and returns an integer representing the maximum path sum starting from the current node.

5. Inside the dfs function, it first checks if the root node is None. If it is None, it means we have reached the end of a branch, so the function returns 0.

6. If the root node is not None, the function recursively calls itself on the left and right child nodes of the current node and assigns the returned values to maxLeft and maxRight variables, respectively.

7. After getting the maximum path sums from the left and right subtrees, the code checks if they are negative (less than 0) and assigns them a value of 0. This step is done to exclude negative contributions from the maximum path sum.

8. The code then calculates the maximum path sum by adding the value of the current node, root.val, to the maximum of maxLeft and maxRight.

9. Next, the code updates the result list by taking the maximum between the current maximum path sum (result[0]) and the maximum path sum that includes the current node (root.val + maxLeft + maxRight).

10. Finally, the dfs function returns the maximum path sum starting from the current node, which is the sum of the current node's value and the maximum of maxLeft and maxRight.

11. Outside the dfs function, the maxPathSum method calls the dfs function with the root node to start the recursion.

12. Finally, the maxPathSum method returns the maximum path sum stored in the result list.

In summary, this code uses a depth-first search approach to recursively calculate the maximum path sum in a binary tree. It keeps track of the maximum path sum encountered so far in the result list, which is updated during the traversal.