437_Path_Sum_iii

Leetcode 437: Path Sum III
Detailed video explanation: https://youtu.be/Vam9gldRapY
============================================

C++:
----
class Solution {
    int pathSum_a(TreeNode* root, int sum){
        if(root == nullptr) return 0;
        int res = 0;
        if(root->val == sum) res++;
        res += pathSum_a(root->left, sum-root->val);
        res += pathSum_a(root->right, sum-root->val);
        return res;
    }
public:
    int pathSum(TreeNode* root, int sum) {
        if(root == nullptr) return 0;
        return pathSum(root->left, sum) + pathSum_a(root, sum) + pathSum(root->right, sum);
    }
};


Java:
----
class Solution {
    private int pathSum_a(TreeNode root, int sum){
        if(root == null) return 0;
        int res = 0;
        if(root.val == sum) res++;
        res += pathSum_a(root.left, sum-root.val);
        res += pathSum_a(root.right, sum-root.val);
        return res;
    }
    public int pathSum(TreeNode root, int sum) {
        if(root == null) return 0;
        return pathSum(root.left, sum) + pathSum_a(root, sum) + pathSum(root.right, sum);
    }
}


Python3:
-------
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        
        def pathSum_a(root, sum):
            if root == None: return 0
            res = 0
            if root.val == sum: res += 1
            res += pathSum_a(root.left, sum-root.val);
            res += pathSum_a(root.right, sum-root.val);
            return res
            
        if root == None: return 0
        return self.pathSum(root.left, sum) + pathSum_a(root, sum) + self.pathSum(root.right, sum)