Help me out , I dont know what is wrong with my recursion equation ..comments are added for clarity


  • 0
    J

    class Solution {

    public:

    int func(TreeNode*root, int *sum) {
        if(!root) {
            *sum=0;
            return 0;
        }
        int lsum,rsum;
        // l is the left subtree's maximum sum path between any 2 nodes
        // r is the right ...
        // lsum is the (left subtree) maximum sum of  path from root to node
        // rsum is the (right subtree) maximum sum of path from root to node
        int l = func(root->left, &lsum);
        int r = func(root->right, &rsum);
        // updating current sum of path to be maximum of left , right path
        *sum = root->val + max(lsum,rsum);
        // return the maximum of sum path from left leaf to right leaf which is stored in sum comparing with maximum of
        // left subtree's computed sum path and right substree....
        return max(*sum, max(l,r));
    }
    int maxPathSum(TreeNode* root) {
        if(!root)
            return 0;
        int sum=INT_MIN;
        return func(root->right, &sum);
    }
    

    };


Log in to reply
 

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