Problem Statement:

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

 

                             5
                            /  \ 
                          4     8
                         /    /  \
                        11    3   4
                       /  \      / \
                      7    2    5   1

               

 

Output:

[5,4,11,2],
[5,8,4,5]

Java Code (Accepted):

class Solution {
void checkIt(int[] arr,int l,List<List<Integer>> ll,int sum)
{
int c=0;
for(int i=0;i<l;i++)
c=c+arr[i];
if(c==sum)
{
List<Integer> al=new ArrayList<Integer>();
for(int i=0;i<l;i++)
al.add(arr[i]);
ll.add(al);
}

}
void printIt(TreeNode root,List<List<Integer>> ll,int sum,int[] arr,int l)
{
if(root==null)
return;

arr[l]=root.val;
l++;
if(root.left==null && root.right==null)
{
checkIt(arr,l,ll,sum);

}

printIt(root.left,ll,sum,arr,l);
printIt(root.right,ll,sum,arr,l);

}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ll=new ArrayList<List<Integer>>();
int[] arr=new int[1000];
printIt(root,ll,sum,arr,0);
return ll;

}
}

 

Pin It on Pinterest