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.
For example, consider a binary tree represented as [1,2,3]
. The optimal path is 2 -> 1 -> 3
with a path sum of 2 + 1 + 3 = 6
.
As another example, consider a binary tree represented as [-10,9,20,null,null,15,7]
. The optimal path is 15 -> 20 -> 7
with a path sum of 15 + 20 + 7 = 42
.
Write an algorithm to efficiently determine the maximum path sum in a given binary tree. What is the time and space complexity of your solution?
A brute-force approach would involve exploring all possible paths in the binary tree and calculating their sums. This could be done using recursion, where we traverse the tree and, at each node, consider paths that include the node and paths that don't. The maximum path sum encountered during this traversal would be the answer.
However, this approach is inefficient because it involves redundant calculations. We would be recalculating the sums of many subpaths multiple times.
A more efficient approach involves using recursion with memoization or dynamic programming principles. We can define a recursive function that returns two values:
We can maintain a global variable to keep track of the maximum path sum encountered so far. During the recursion, we update this variable whenever we find a path with a greater sum.
class Solution {
int max_sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
return max_sum;
}
private int maxPathSumHelper(TreeNode node) {
if (node == null) return 0;
int left = Math.max(maxPathSumHelper(node.left), 0);
int right = Math.max(maxPathSumHelper(node.right), 0);
int price_newpath = node.val + left + right;
max_sum = Math.max(max_sum, price_newpath);
return node.val + Math.max(left, right);
}
}
max_sum
: A global variable to store the maximum path sum found so far, initialized to the smallest possible integer value.maxPathSum(TreeNode root)
: The main function that initiates the recursive calculation.maxPathSumHelper(TreeNode node)
: A recursive helper function that calculates the maximum path sum.
price_newpath
).max_sum
if price_newpath
is greater than the current max_sum
.