C++ recursive solution using pair to track results

  • 0

    the first element in pair is the maximum single pathsum
    the second element in pair is the maximum pathsum for the subtree root at given node

    class Solution {
        int maxPathSum(TreeNode* root) 
            if(!root) return 0;
            return help(root).second;
        pair<int,int> help(TreeNode* root)
            if(!root) return make_pair(INT_MIN,INT_MIN);
            pair<int,int>left = help(root->left), right = help(root->right);
            int first = root->val + max(max(0, left.first), max(0, right.first));
            int second = root->val + max(0, left.first) + max(0, right.first);
            return make_pair(first, max(second, max(left.second, right.second)));

Log in to reply

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