# My Java solution with DFS, BFS and recursion

• recursion:

``````public class Solution {
//pre order
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> list=new ArrayList<List<Integer>>();

makeList(list,root,new ArrayList<Integer>(),sum);
return list;
}

private void makeList(List<List<Integer>> list, TreeNode node, List<Integer> path, int sum) {
if (node==null) return;
if (node.left==null && node.right==null && node.val==sum) {
return;
}
makeList(list, node.left, new ArrayList<Integer>(path),sum-node.val);
makeList(list, node.right, new ArrayList<Integer>(path),sum-node.val);
}
}
``````

DFS - stack:

``````public class Solution {
//DFS - Stack
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> list=new ArrayList<List<Integer>>();

if (root==null) return list;

while (!qNode.isEmpty()) {
TreeNode curNode=qNode.remove();
int curSum=qSum.remove();
List<Integer> curList=qList.remove();

if (curNode.left==null && curNode.right==null && curNode.val==curSum)
if (curNode.left!=null) {
}
if (curNode.right!=null) {
}
}
return list;
}

}
``````

BFS - queue

``````public class Solution {
//BFS - queue
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> list=new ArrayList<List<Integer>>();

if (root==null) return list;

while (!qNode.isEmpty()) {
TreeNode curNode=qNode.remove();
int curSum=qSum.remove();
List<Integer> curList=qList.remove();

if (curNode.left==null && curNode.right==null && curNode.val==curSum)
if (curNode.left!=null) {
}
if (curNode.right!=null) {