Easy to understand recursive C++ solution with explanation


  • 0
    P

    We can find the solution in either of the 3 manners

    1. Some path adds up to sum from the root (i.e. root is a member of the path)
    2. Root is not a member of the path and solution lies completely in left sub-tree
    3. Root is not a member of the path and solution lies completely in right sub- tree

    2 & 3 are taken care of by recursion in the function pathSum()

    Case 1 is taken care of in pathSumRec() function.
    In this the solution can be reached in three steps again.

    1. Root == sum
    2. Root + some path in left subtree
    3. Root + some path in right subtree
    
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
    
        int pathSumRec(TreeNode* root, int sum) {
            
            if(root == NULL)
                return 0;
            
            int rootmatch =  (root->val == sum);
            int left = pathSumRec(root->left, sum - root->val);
            int right = pathSumRec(root->right, sum - root->val);
            
            return rootmatch + left + right;
            
        }
    
    
        int pathSum(TreeNode* root, int sum) {
            
            if (root == NULL)
                return 0;
            
            int rootval =  pathSumRec(root, sum);
            int lefttree = pathSum(root->left, sum);
            int righttree = pathSum(root->right, sum);
            return (rootval + lefttree + righttree);
            
            
        }
    };
    
    

Log in to reply
 

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