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.

Comments

  1. If we initialize maxsum=INT_MIN

    Then 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 ?

    ReplyDelete
    Replies
    1. You are absolutely right. There is no need to use flag. Thanks :)

      Delete
  2. I 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:

    {
    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.

    ReplyDelete
  3. Sorry, about the partial code above. Here's the full version:

    public 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;
    }

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. Hi 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
    if (!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!

    ReplyDelete

Post a Comment

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs