Binary Tree Maximum Path Sum
Problem Description
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:
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.
Example 2:
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
Solve it on LeetCode
Approaches
1. Recursive Brute Force
Intuition:
The basic idea is to traverse each node of the binary tree and determine all possible paths that can be formed with this node as part of the path. Note that a path can start and terminate at any node, however, this approach might result in revisiting nodes multiple times causing inefficiency.
Steps:
- We define a recursive function that will explore the different possible paths in the left and right subtrees.
- At each node, consider four possibilities:
- Node alone (no children).
- Node with its left subtree.
- Node with its right subtree.
- Node with both left and right subtree as the change in path.
- The maximum of these four possibilities gives the maximum path sum at that node.
- Keep track of the global maximum path sum encountered during the traversal.
Code:
- Time Complexity: O(N^2) where N is the number of nodes because each node invocation leads to exploring its children in separate recursions.
- Space Complexity: O(H) where H is the height of the tree, representing the depth of the recursion stack.
2. Optimized Recursive with Global Maximum
Intuition:
To optimize, we need to ensure that we only compute each subtree path sum once per node. This can be achieved by using a helper function that returns not only the maximum path sum that can include the ancestor of the current node, but also updates a global maximum variable which tracks the most optimal path seen so far.
Steps:
- We use a helper function
maxGainthat computes the maximum gain from each node. - Use a global variable
maxSumto keep track of the maximum path sum encountered. - If the contribution from a subtree is negative, it is better to avoid including that subtree.
- At each node, compute the max gain through the node which can be passed to its parent.
- This is done by taking the maximum of 0 and the gain from the left and right subtree, adding the current node's value.
Code:
- Time Complexity: O(N) since each node is processed exactly once.
- Space Complexity: O(H) where H is the height of the tree for the recursion stack.