113. 路径总和 II【中等】
题解前置题是112. 路径总和【简单】,这道题在之前的基础上要求了具体路径,而不是只求有没有
BFS代码与前置题类似,多的一点是需要建立父子结点的映射map,等遍历到叶子结点,发现路径和满足条件时,可顺着叶子结点向上返回该路径
class Solution {
List>paths=new ArrayList<>();
Mapmap=new HashMap<>();//存放父子关系
public List> pathSum(TreeNode root, int targetSum) {
if(root==null)
return paths;
QueuenodeQueue=new LinkedList<>();//结点队列
QueuesumQueue=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){
Listlist=new ArrayList<>();
while(node!=null){
list.add(node.val);//存入结点的值
node=map.get(node);//找父结点
}
Collections.reverse(list);
paths.add(list);
}
}
时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n ) O(n) O(n)
DFS用双端队列记录路径,dfs一次最后在队列末尾弹出一个元素(像回溯?)
class Solution {
List>paths=new ArrayList<>();//所有路径
Dequepath=new LinkedList<>();
public List> 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^2) O(n2)
空间复杂度: O ( n ) O(n) O(n)



