Accepted 10-line c++ solution, 19ms


  • 0
    P

    Maintain ll and rl for left and right subtree respectively. They stand for the largest sum along the path with current node as starting point, or a void path, in order to "connect" it to another path at current node to achieve longer path with larger sum. If the largest possible sum of the path including current node is less than 0, the corresponding path will no longer be a part of the final path. Here is the explanation:

    Assume we have current node pathB = current-...-end, we have a path: pathA-pathB, if the sum of pathB is less than 0, then the sum of pathA-pathB is less than pathA. Therefore we exclude pathB.

    class Solution {
    public:
        int helper(TreeNode* x, int &line) {
            if (x == NULL) return INT_MIN;
            int ll = 0, rl = 0, lm = helper(x->left, ll), rm = helper(x->right, rl);
            line = max(0, max(ll, rl) + x->val);
            return max(ll + rl + x->val, max(lm, rm));
        }
        int maxPathSum(TreeNode* root) {
            int line = 0;
            return helper(root, line);
        }
    };
    

Log in to reply
 

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