Simple O(n) algorithm with one traversal through the tree


  • 73
    X
    class Solution {
        int maxToRoot(TreeNode *root, int &re) {
            if (!root) return 0;
            int l = maxToRoot(root->left, re);
            int r = maxToRoot(root->right, re);
            if (l < 0) l = 0;
            if (r < 0) r = 0;
            if (l + r + root->val > re) re = l + r + root->val;
            return root->val += max(l, r);
        }
    public:
        int maxPathSum(TreeNode *root) {
            int max = -2147483648;
            maxToRoot(root, max);
            return max;
        }
    };
    

    update the val of each node of the tree bottom-up, the new val of TreeNode *x stands for the max sum started from any node in subtree x and ended in x, mataining the re for result in traversal at the same time.


  • 0
    N

    Smart thought!
    Help me a lot!
    Thx!


  • 6
    B

    Oops. Sorry, clicked the wrong arrow. I meant to click the vote +1


  • 27
    A

    Good solution! Essentially same as mine, but I don't see why you update the val of each node, since each node is visited only once. In my version, I just return the maximum path ending at the root of the current tree while potentially updating the value of the global maximum with the path that links left and right.

    class Solution {
    public:
        int maxPathSum(TreeNode *root) {
            int max = numeric_limits<int>::min();
            maxPathAndGlobalUpdate(root, &max);
            return max;
        }
    private:
        int maxPathAndGlobalUpdate(TreeNode *root, int* _global_max) {
            if (root == nullptr) return 0;
            int& global_max = *_global_max;
            int l = max(0, maxPathAndGlobalUpdate(root->left, &global_max));
            int r = max(0, maxPathAndGlobalUpdate(root->right, &global_max));
            global_max = max(global_max, l + r + root->val);
            return root->val + max(l, r);
        }
    };

  • 2
    X

    updating is not necessary indeed...


  • 0
    C

    really smart solution!


  • 0
    Z

    Strictly speaking, the new value of TreeNode *x represents the maximum sum of the downward path starting from x. For example, consider the subtree {1, 2, 3}. The new value for node 1 will be 1+3 = 4 not 1+2+3 = 6.


  • 0
    S

    I don't think your solution is right, have you thought the case all the nodes with the negative values?! This case also exits max sum!!


  • 0
    A

    In case all nodes have negative values, the path with maximum sum is the empty path (no nodes in it). The sum of such path is zero, which is what my solution returns.


  • 0
    S

    Thanks, this is also a way of thinking about this problem! I got you! Nice Day!


  • 0
    A

    You're welcome! Thanks to you for the comment :)


  • 0
    J

    what if tree is -2, 5.. Your algo returns 5 shouldnt it be 3? Because maximum between two nodes is asked


  • 0
    Z

    I think that the path can start and end at the same node, so 5 should be the correct answer in this case.


  • 0
    S

    Can you please explain in maxtoRoot function, why do you return "root->val += max(l, r) " instead of "root->val+= l + r" if both left and right are positive ? Thank you


  • 0
    Z

    The maxToRoot return value is the maximum path starting from the root, not the maximum path including the root. If we return the maximum path including the root which may contain the nodes in both the left and right subtrees, this maximum path can't be used to form a path including the parent of the root.


  • 1

    Why do you write return root->val += max(l, r); instead of return root->val + max(l, r); :-)


  • 0

    Well, learn a new thing numeric_limits<int>::min() :-)


  • 0
    Z

    The solution was posted by xt2357, not me, so I can't speak for him/her. IMHO, "+=" and "+" are both correct but it is better to use "+" here since it won't modify the node value. Thank you for pointing this out.


  • 0
    R

    Hi, I wonder if it could be possible to reduce the space complexity of the method with using morris tree traversal? Does anyone have idea if it is possible or not ?


  • 0
    Z

    Great!!! Thanks a lot!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.