# Accepted recursive and non-recursive Java Solutions ( 7/15 ms)

• ``````public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> rs = new ArrayList<List<Integer>>();
if (root == null) {
return rs;
}
//searchPathSumRecur(root, sum, 0, new ArrayList<Integer>(), rs);

TreeNode p = root;
Stack<TreeNode> S = new Stack<TreeNode>();
int curSum = 0;
Map<TreeNode,List<Integer>> map1 = new HashMap<TreeNode,List<Integer>>();
Map<TreeNode,Integer> map2 = new HashMap<TreeNode,Integer>();
List<Integer> tmp = new ArrayList<Integer>();
while (S.isEmpty() == false || p != null) {
if (p != null) {
curSum += p.val;
S.push(p);
map1.put(p, new ArrayList<Integer>(tmp));
map2.put(p, curSum);
if (p.left == null && p.right == null && curSum == sum){
}
p = p.left;
} else{
p = S.pop();
tmp = map1.get(p);
curSum = map2.get(p);
p = p.right;
}
}
return rs;
}

public void searchPathSumRecur(TreeNode root, int sum, int curSum, List<Integer> cur, List<List<Integer>> rs) {
if (root.left == null && root.right == null && curSum + root.val == sum){
} else {
if(root.left != null){
searchPathSumRecur(root.left, sum, curSum + root.val, new ArrayList<Integer>(cur), rs);
}
if(root.right != null){
searchPathSumRecur(root.right, sum, curSum + root.val, new ArrayList<Integer>(cur), rs);
}
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.