Skip to content

Instantly share code, notes, and snippets.

@shharma-vipin
Created August 11, 2019 12:31
Show Gist options
  • Save shharma-vipin/bc849de2b60e4553cbc694f14cb673d1 to your computer and use it in GitHub Desktop.
Save shharma-vipin/bc849de2b60e4553cbc694f14cb673d1 to your computer and use it in GitHub Desktop.
Sum Of path equal to K in binary tree
public ArrayList<ArrayList<Integer>> pathSum(TreeNode A, int B) {
if(A == null) return null;
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
Deque<TreeNode> deque = new ArrayDeque();
doItNow(A,B,deque,res);
return res;
}
private void doItNow(TreeNode n, int m, Deque<TreeNode> deque,ArrayList<ArrayList<Integer>> res){
if(n == null) return;
deque.addLast(n);
if(isLeaf(n)){
checkSumForPath(deque,m,res);
}
doItNow(n.left,m,deque,res);
doItNow(n.right,m,deque,res);
deque.removeLast();
}
private void checkSumForPath(Deque<TreeNode> queue, int sum, ArrayList<ArrayList<Integer>> res){
if(queue == null) return;
int tempVar = sum;
ArrayList<Integer> tempList = new ArrayList<>();
Deque<TreeNode> tempQueue = new ArrayDeque<>();
while(!queue.isEmpty()){
TreeNode temp = queue.remove();
tempVar -= temp.val;
tempQueue.add(temp);
}
while(!tempQueue.isEmpty()){
TreeNode temp = tempQueue.remove();
queue.add(temp);
if(tempVar == 0){
tempList.add(temp.val);
}
}
if(!tempList.isEmpty()){
res.add(tempList);
}
}
private boolean isLeaf(TreeNode node){
return node.left == null && node.right == null;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment