Path Sum III

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

Example:

      10
     /  \
    5   -3
   / \    \
  3   2   11 sum=8
Output: 2

Approach

Java

public class PathSumIII {
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(10);
        tree.left = new TreeNode(5);
        tree.left.left = new TreeNode(3);
        tree.left.right = new TreeNode(2);
        tree.right = new TreeNode(-3);
        tree.right.right = new TreeNode(11);
        int sum = 8;
        System.out.println(pathSum(tree, sum));
    }

    static int dfs(TreeNode root, int sum) {

        // if tree is empty
        if (root == null)
            return 0;
        // call for left and right
        int f = 0;
        if (root.val == sum)
            f = 1;
        return f + dfs(root.left, sum - root.val) +
                     dfs(root.right, sum - root.val);

    }

//function to count number of
//path with the given sum
    static int pathSum(TreeNode root, int sum) {
        if (root == null)
            return 0;
        return dfs(root, sum) + pathSum(root.left, sum) + 
                        pathSum(root.right, sum);
    }

}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};


int dfs(TreeNode *root,int sum)
{

    //if tree is empty
     if(root==NULL)
               return 0;
      //call for left and right
     return (root->data==sum)+dfs(root->left,sum-root->data)
              +dfs(root->right,sum-root->data);
}

//function to count number of
//path with the given sum
int pathSum(TreeNode* root, int sum) 
{
    if(root==NULL)
         return 0;
     return dfs(root,sum)+pathSum(root->left,sum)
         +pathSum(root->right,sum);
}

int main()
{

   TreeNode *root=new TreeNode(10);
   root->left=new TreeNode(5);
   root->right=new TreeNode(-3);
   root->left->left=new TreeNode(3);
   root->left->right=new TreeNode(2);
   root->right->right=new TreeNode(11);
   int sum=8;
   cout<<pathSum(root,sum);
   return 0;
}