In this Leetcode Path Sum problem solution we have Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children.

Leetcode Path Sum problem solution


Problem solution in Python.

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        def helper(node, target):
            if not node:
                return False
            
            target -= node.val
            
            if (target == 0) and (not node.left) and (not node.right):
                return True
            
            return helper(node.left, target) or helper(node.right, target)
        
        if not root:
            return
        
        return helper(root, sum)



Problem solution in Java.

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        return hasPathSum(root, sum, 0);
    }
    
    private boolean hasPathSum(TreeNode root, int sum, int temp) {
        if(root == null) {
            return false;
        }
        temp += root.val;
        if(temp == sum && root.left == null && root.right == null) {
            return true;
        }
        return hasPathSum(root.left, sum, temp) || hasPathSum(root.right, sum, temp);
    }
}


Problem solution in C++.

class Solution {
public:
    void f(TreeNode* root, int targetSum, int contri, int &ans) {
        if(root == NULL)
            return;
        
        if(root->left == NULL && root->right == NULL) {
            if(contri+root->val == targetSum) ans = 1;
            return;
        }
        
        f(root->right, targetSum, contri+root->val, ans);
        f(root->left, targetSum, contri+root->val, ans);
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        int ans = 0, contri = 0;
        
        f(root, targetSum, 0, ans);
        
        return ans;
    }
};


Problem solution in C.

typedef struct TreeNode t;

void getSum(t* root, int target, int* sum,bool* ret){
    if(!root->left && !root->right) {
        if((*sum) + root->val == target){
            *ret=1;
        }
        return;
    }
    (*sum)+=root->val;
    if(root->left) {
        getSum(root->left,target,sum,ret);
    }
    if(root->right) {
        getSum(root->right,target,sum,ret);
    }
    (*sum)-=root->val;
    
}

bool hasPathSum(t* root, int sum){
    if(!root) return 0;
    int s=0;
    bool ret=0;
    getSum(root,sum,&s,&ret);
    return ret;
}