A simple recursive solution in CPP w/ explanation


  • 0
    B

    The basic idea is to go all the way from the root down to left nodes, and minus the sum by the node's valuable along the path. When we reach the leaf nodes, see if the sum becomes to zero, if so, we have the sum path.

    class Solution {

    public:
    
    bool hasPathSum(TreeNode* root, int sum) {
       
        if(root == NULL){
            return false;
        }
        if(root -> left == NULL && root -> right == NULL){
            return sum - root -> val == 0;
        }
        return hasPathSum(root -> left, sum - root -> val) || hasPathSum(root -> right, sum - root -> val);
    }
    

    };


Log in to reply
 

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