Accepted O(n), O(1) solution


  • 1
    N
    class Solution {
    public:
    	int maxPathSum(TreeNode *root) {
    		if(!root) return 0;
    		maxSum = root->val;
    		recNodes(root); 
    		return maxSum;
    	}
    
    protected:
    	int recNodes(TreeNode* node)
    	{
    		int numl=0,numr=0;
    		if (node->left)
    			numl = recNodes(node->left);
    		if (node->right)
    			numr = recNodes(node->right);
    
    		//choose the max path, either left or right	
    		int value = node->val;
    		int sumWhole = checkMax(value,numl+numr);
    		int sumLeft = numl>0?checkMax(value,numl):value;
    		int sumRight = numr>0?checkMax(value,numr):value;
    
    		return max(sumLeft,sumRight);
    	}
    
    	int checkMax(int value, int sum)
    	{
    		if(sum>0)
    			sum+=value;
    		else
    			sum=value;
    		if(sum>maxSum)
    			maxSum = sum;
    		return sum;
    	}
    
    	int maxSum;
    };

Log in to reply
 

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