题目

113. 路径总和 II【中等】

题解

前置题是112. 路径总和【简单】，这道题在之前的基础上要求了具体路径，而不是只求有没有

BFS

代码与前置题类似，多的一点是需要建立父子结点的映射map，等遍历到叶子结点，发现路径和满足条件时，可顺着叶子结点向上返回该路径

class Solution {List<List<Integer>>paths=new ArrayList<>();Map<TreeNode,TreeNode>map=new HashMap<>();//存放父子关系public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if(root==null)return paths;Queue<TreeNode>nodeQueue=new LinkedList<>();//结点队列Queue<Integer>sumQueue=new LinkedList<>();//路径和队列nodeQueue.offer(root);sumQueue.offer(0);while(!nodeQueue.isEmpty()){TreeNode node=nodeQueue.poll();int sum=node.val+sumQueue.poll();if(node.left==null&&node.right==null){if(sum==targetSum)getPath(node);}if(node.left!=null){sumQueue.offer(sum);//当前路径和存入队列map.put(node.left,node);//存入儿子父亲nodeQueue.offer(node.left);}if(node.right!=null){sumQueue.offer(sum);map.put(node.right,node);nodeQueue.offer(node.right);}}return paths;}//满足条件的路径加入结果集public void getPath(TreeNode node){List<Integer>list=new ArrayList<>();while(node!=null){list.add(node.val);//存入结点的值node=map.get(node);//找父结点}Collections.reverse(list);paths.add(list);}
}

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

DFS

用双端队列记录路径，dfs一次最后在队列末尾弹出一个元素（像回溯？）

class Solution {List<List<Integer>>paths=new ArrayList<>();//所有路径Deque<Integer>path=new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {dfs(root,targetSum);return paths;}public void dfs(TreeNode root, int targetSum) {if(root==null)return;path.offer(root.val);//结点加入路径targetSum-=root.val;if(root.left==null&&root.right==null){if(targetSum==0)paths.add(new LinkedList<>(path));}pathSum(root.left,targetSum);pathSum(root.right,targetSum);path.pollLast();//“队尾”弹出元素！}
}

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$