Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
Solution:
For root node, first check two subtrees and figure out the path with maximum sum in each subtree (and the path must contains the root node). More precisely, we can compare root->val, root->val + leftsubtree, root->val + rightsubtree.
But this is not enough since the maximum path might contains two subtrees. We have to compute the value of root->val + leftsubtree + rightsubtree as well. The problem is, we cannot directly return this value since this path cannot go to upper nodes anymore. So we also use another global variable to store the maximum sum in each recursion, and update this variable once we find any path with larger sum.
The following code passes the LeetCode Online Large Judge. Thanks for the useful comments.
The path may start and end at any node in the tree.
Solution:
For root node, first check two subtrees and figure out the path with maximum sum in each subtree (and the path must contains the root node). More precisely, we can compare root->val, root->val + leftsubtree, root->val + rightsubtree.
But this is not enough since the maximum path might contains two subtrees. We have to compute the value of root->val + leftsubtree + rightsubtree as well. The problem is, we cannot directly return this value since this path cannot go to upper nodes anymore. So we also use another global variable to store the maximum sum in each recursion, and update this variable once we find any path with larger sum.
The following code passes the LeetCode Online Large Judge. Thanks for the useful comments.
If we initialize maxsum=INT_MIN
ReplyDeleteThen can we replace this code
==================================
if (flag) {
maxsum = max(csum, node->val + lsum + rsum);
flag = false;
}
else {
maxsum = max(maxsum, max(csum, node->val + lsum + rsum));
}
==================================
with
==================================
maxsum = max (maxsum, max(csum, node->val + lsum + rsum));
==================================
I got confused why is there bool flag needed ?
You are absolutely right. There is no need to use flag. Thanks :)
DeleteI tried to implement a similar algorithm in C# but couldnt get it to work with all the test cases. My code looks something like this:
ReplyDelete{
if (node == null) {
return 0;
}
int maxLeft = MaxPathSum (node.left, maxSum);
int maxRight = MaxPathSum (node.right, maxSum);
int sum1 = Math.Max (node.data, Math.Max (maxLeft + node.data, maxRight + node.data));
int sum2 = Math.Max (maxSum, sum1);
maxSum = Math.Max (sum2, node.data + maxLeft + maxRight);
return maxSum;
}
Could you provide a C# version of your code or if you can see anything strikingly weird about my code above, please point it out for me! Thanks.
Sorry, about the partial code above. Here's the full version:
ReplyDeletepublic int MaxSum(BinaryTreeNode node)
{
return MaxPathSum (node, 0);
}
public int MaxPathSum(BinaryTreeNode node, int maxSum)
{
if (node == null) {
return 0;
}
int maxLeft = MaxPathSum (node.left, maxSum);
int maxRight = MaxPathSum (node.right, maxSum);
int sum1 = Math.Max (node.data, Math.Max (maxLeft + node.data, maxRight + node.data));
int sum2 = Math.Max (maxSum, sum1);
maxSum = Math.Max (sum2, node.data + maxLeft + maxRight);
return maxSum;
}
Sorry I am not familiar with C#...
DeleteThis comment has been removed by the author.
ReplyDeleteHi Hao Feng! Thanks for your post! I came across it when I was trying to solve it on the Leet Code. It is a really neat idea although I would like to point out it might not work if the max_sum at certain node is negative. I changed
ReplyDeleteif (!node) {
csum = 0;
return;
}
to
if (!node) {
csum = 0;
max_sum=max(INT_MIN,max_sum);
return;
}
and I think that would take care of the negative cases. Again, nice work!