C++ 8 line recursive solution w/ explanation.


  • 2
    C
    // Very cool problem! Here is my solution:
    // MaxPaths stores 2 candidates:
    //      1. (path that goes through me, possibly down to lhs or rhs , AND
    //      2. path that goes from my lhs, through me, cross to rhs)
    //         note that first result only eats up one node, 
    //         while second result is complete (eats both src and dst nodes)
    //         [By complete, I mean that we can't add on nodes to this path in recursion]
    //
    // To find maxSumPath of the entire tree, we do this recursively
    // For (1) [remember this choice only consumes 1 node]
    //     a. choose a path that goes through me concat w/ best lhs path OR
    //     b. choose a path that goes thorugh me concat w/ best rhs path OR
    //     c. Or just myself only (if lhs and rhs are all -ve for example!)
    //
    // For (2), we have the following candidates:
    //      my cross path could be either
    //       a. from me to my lhs' best end
    //       b. from me to my rhs' best end
    //       c. from myself to myself
    //       d. from somewhere in my lhs, through me, to somewhere in my rhs (myCrossPath)
    //       e. my lhs' crosspath
    //       f. my rhs' crosspath
    //     Note that a, b, c above are same as first case! So I can re-use that computation!
    
    class Solution {
        typedef pair<int, int> MaxPaths; 
        
        MaxPaths maxPathSumPrime(TreeNode* root) {
            if (root == NULL) return (make_pair(0, std::numeric_limits<int>::min()));
            MaxPaths lhsResults = maxPathSumPrime(root->left);
            MaxPaths rhsResults = maxPathSumPrime(root->right);
            int justMe    = root->val;
            int myCrossPath = lhsResults.first + rhsResults.first + justMe;
            int myfirst = std::max(justMe, std::max(lhsResults.first + justMe, rhsResults.first + justMe));
            int mysecond = std::max(myfirst, std::max(myCrossPath, std::max(lhsResults.second, rhsResults.second)));
            return (make_pair(myfirst, mysecond));
        }
    public:
        int maxPathSum(TreeNode* root) {
            MaxPaths result = maxPathSumPrime(root);
            return (std::max(result.first, result.second));
        }
    };

Log in to reply
 

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