来源：LeetCode
难度：中等
描述：
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例1：
输入:root= [5，4，8，11，null，13，4，7，2，null，null，5，1]，targetSum=22
输出：[[5,4,11,2]，[5,8,4,5]]
示例2：
分析：本题要求找出所有从根节点到叶子节点 路径总和等于给定目标和的路径，对于这类求所有可能性的题目，自然而然想到回溯法，由于给出的是一颗二叉树，咱们采用深度优先遍历的方式遍历二叉树，往下走一步，将targetSum减去本节点的值（也可采用节点值累加向下传递的方式），如下图
题外话：对于求所有解，一般都能采用回溯法，使用回溯法时注意好choose、explore、un choose三步骤即可
解题
方法一：回溯法 + dfs解题
思路：对于二叉树深度优先遍历，先遍历左子树，再遍历右子树，先判断了当前节点的左子树或右子树不为空，再 choose 当前值，当满足条件时，将满足条件节点的值，加入到集合中，注意回退时要剪枝
代码：
1public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
2 List<List<Integer>> res = new ArrayList<>();
3 if(null == root) return res;
4 dfs(root, targetSum, res, new ArrayList<Integer>());
5 return res;
6}
7
8private void dfs(TreeNode root, int targetSum,
9 List<List<Integer>> res, List<Integer> cur) {
10 // 左右子树均为空，说明当前节点是一个叶子节点
11 if (root.left == null && root.right == null) {
12 // 满足条件。注意，将最后一个元素加入到集合中
13 if (targetSum - root.val == 0) {
14 cur.add(root.val);
15 //add时创建新数组，防止一直沿用到一个数组
16 res.add(new ArrayList<>(cur));
17 //回溯 剪枝
18 cur.remove(cur.size() - 1);
19 }
20 return;
21 }
22 // 遍历左子树
23 if (root.left != null) {
24 // choose
25 cur.add(root.val);
26 // explore
27 dfs(root.left, targetSum - root.val, res, cur);
28 // un choose
29 cur.remove(cur.size() - 1);
30 }
31 // 遍历右子树
32 if (root.right != null) {
33 // choose
34 cur.add(root.val);
35 // explore
36 dfs(root.right, targetSum - root.val, res, cur);
37 // un choose
38 cur.remove(cur.size() - 1);
39 }
40}代码写法优化，提前将本节点放入集合内：
1public List<List<Integer>> pathSum(TreeNode root, int sum) {
2 if (root == null) {
3 return null;
4 }
5 List<List<Integer>> result = new ArrayList<>();
6 pathSumList(root, sum, result, new ArrayList<>());
7 return result;
8}
9
10private void pathSumList(TreeNode root, int sum,
11 List<List<Integer>> result, List<Integer> cur) {
12 if (root == null) {
13 return;
14 }
15 //提前将本节点添加进数组
16 cur.add(root.val);
17 if (root.left == null && root.right == null) {
18 if (root.val == sum) {
19 //重新创建数组 防止一直使用一个数组
20 result.add(new ArrayList<>(cur));
21 }
22 //剪枝 去掉本节点
23 cur.remove(cur.size() - 1);
24 return;
25 }
26 //左子树
27 pathSumList(root.left, sum - root.val, result, cur);
28 //右子树
29 pathSumList(root.right, sum - root.val, result, cur);
30 //剪枝 去掉本节点
31 cur.remove(cur.size() - 1);
32}方法二：广度优先遍历解题
思路：通过广度优先遍历二叉树，采用两个队列分别存储当前节点以及到达当前节点的路径节点值，当 当前节点为叶子节点且值和目的值一致时，将该条路径放入结果集当中
代码：
1public List<List<Integer>> pathSum(TreeNode root, int sum) {
2 List<List<Integer>> res = new ArrayList<>();
3 //如果节点为空直接返回
4 if (root == null) {
5 return res;
6 }
7 //使用两个队列，一个存储结点，一个存储从更结点到当前节点的路径
8 Queue<TreeNode> queueNode = new LinkedList<>();
9 Queue<List<Integer>> queueList = new LinkedList<>();
10 //根节点入队
11 queueNode.add(root);
12 //根节点的路径入队
13 List<Integer> list = new ArrayList<>();
14 list.add(root.val);
15 queueList.add(list);
16 while (!queueNode.isEmpty()) {
17 //当前节点出队
18 TreeNode node = queueNode.poll();
19 //当前节点的路径出队
20 List<Integer> tempList = queueList.poll();
21 if (node.left == null && node.right == null && node.val == sum) {
22 //如果满足条件，就把路径存储到res中
23 res.add(tempList);
24 }
25 //左子节点不为空，左子节点和路径入队
26 if (node.left != null) {
27 tempList.add(node.left.val);
28 queueList.add(new ArrayList<>(tempList));
29 //将本节点值累加到其左右节点上去
30 node.left.val += node.val;
31 queueNode.add(node.left);
32 //由于还有右节点，且左节点已加入到List当中，故需剔除该左节点值
33 tempList.remove(tempList.size() - 1);
34 }
35 //右子节点不为空，右子节点和路径入队
36 if (node.right != null) {
37 tempList.add(node.right.val);
38 queueList.add(new ArrayList<>(tempList));
39 //将本节点值累加到其左右节点上去
40 node.right.val += node.val;
41 queueNode.add(node.right);
42 }
43 }
44 return res;
45}以上仅是个人思路解法
转载请注明：XAMPP中文组官网 » 数组篇5_路径总和 II解题思路