【dfs回溯】 113 路径总和

题目

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 给定如下二叉树，以及目标和 sum = 22， 5 / 4 8 / / 11 13 4 / \ / 7 2 5 1

返回：[ [5,4,11,2], [5,8,4,5] ]

思路

dfs回溯。必须是结尾为叶子节点时才加入列表。 剪枝是：当左孩子为空就遍历右，右为空就遍历左。因为如果不剪枝，当遍历到叶子节点的时候，会遍历一次叶子节点的左孩子遍历一次叶子节点的右孩子，就会有两个重复解。

代码

public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new ArrayList<>(); Deque<Integer> path = new ArrayDeque<>(); if(root==null) return res; dfs(root,sum,path,res); return res; } /* def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择 */ public void dfs(TreeNode root, int sum, Deque<Integer> path, List<List<Integer>>res){ //要求是到叶子节点的路径，因此只有当两个条件都满足才加入集合 if(root==null) { if(sum==0){ res.add(new ArrayList<>(path)); } return; } path.add(root.val); if(root.right==null){ dfs(root.left,sum-root.val,path,res); }else if(root.left==null){ dfs(root.right,sum-root.val,path,res); } else{ dfs(root.left,sum-root.val,path,res); dfs(root.right,sum-root.val,path,res); } path.removeLast(); }