Bottom Up Solution in C++


  • 0
    G
    class Solution {
    public:
    
        int getMaxPath(TreeNode *root,int &MaxSF)
        {
            if(root == NULL)
            {
                MaxSF = 0;
                return (INT_MIN);
            }
            
            int LeftSF = 0, RightSF = 0;
            
            int Res1 = getMaxPath(root->left,LeftSF);
            int Res2 = getMaxPath(root->right,RightSF);
            
            MaxSF = max(root->val,max(root->val + LeftSF,root->val + RightSF));
            return  max(Res1,max(Res2,max(MaxSF,root->val + LeftSF + RightSF)));
        }
    
        int maxPathSum(TreeNode* root) 
        {
            int MaxST = 0;
            
            return
            getMaxPath(root,MaxST);    
        }
    };
    

Log in to reply
 

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