import java.util.ArrayList; /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { if(root == null) return res; // 错误情况特判 ArrayList<Integer> list = new ArrayList<>(); dfs(root,target,list); // 深度遍历 return res; } void dfs(TreeNode root, int target, ArrayList<Integer> list){ if(root == null) return; if(root.left == null && root.right==null){ // 递归终止条件 if(root.val == target) { list.add(root.val); res.add(list); } } ArrayList<Integer> newList1 = new ArrayList<>(); newList1.addAll(list); newList1.add(root.val); dfs(root.left,target-root.val,newList1); ArrayList<Integer> newList2 = new ArrayList<>(); newList2.addAll(list); newList2.add(root.val); dfs(root.right,target-root.val,newList2); } }
写一个深度搜索即可解决:每次往下的时候保存一下经过的路径,且target的目标值减去路径上结点的值。
到叶子结点时,如果target正好等于叶节点的值, 说明这是一条符合要求的路径;否则直接丢弃之前的路径