Simple and easy understood recursive c++ code with O(n) time


  • 4
    X
    class Solution {
    public:
        int maxPathSum(TreeNode *root) {
            buildVector(root);
            return maxVal;
        }
        int buildVector(TreeNode *root){
            if(!root)
                return 0;
            int left = buildVector(root->left);
            int right = buildVector(root->right);
            //assume this node as root and calcu maxVal based on it
            int sum = root->val;
            if(left > 0)
                sum += left;
            if(right > 0)
                sum += right;
            if(sum > maxVal)
                maxVal = sum;
            //return val is either left or right node with this node
            left = left > right ? left : right;
            sum = root->val;
            if(left > 0)
                sum += left;
            return sum;
        }
    private:
        int maxVal = INT_MIN;
    };

  • -3
    D

    understand why such recurstion lsum, rsum and result is passed with pointer here at with same code and same example : http://goo.gl/wuatmP


Log in to reply
 

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