https://leetcode.com/problems/path-sum-ii/
DFS, Backtracking1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> pathList=new ArrayList<>();
List<Integer> pathNodes=new ArrayList<>();
recurseTree(root,sum,pathNodes,pathList);
return pathList;
}
private void recurseTree(TreeNode root,int remainingSum,List<Integer> pathNodes,List<List<Integer>> pathList){
if(root==null) return;
pathNodes.add(root.val);
if(remainingSum==root.val&&root.left==null&&root.right==null){
pathList.add(new ArrayList(pathNodes));
}else{
recurseTree(root.left,remainingSum-root.val,pathNodes,pathList);
recurseTree(root.right,remainingSum-root.val,pathNodes,pathList);
}
pathNodes.remove(pathNodes.size()-1);
}
}