目录
0. 前言
这道题目是112. 路径总和 - 力扣（LeetCode）的进阶,
做完之后你将会通过dfs, 对回溯算法更加熟悉。
其他回溯的题还有算法：leetcode_129_求根节点到叶节点数字之和-CSDN博客
前一篇分享的路径总和Ⅰ博客已经做了详细讲解：
太君这边请：算法：leetcode_112_路径总和-CSDN博客
1. 题目介绍
2. 思路
这道题目和112. 路径总和最明显的区别就是：
需要将从根节点到叶子节点符合要求的所有路径都记录下来。
接下来跟着我的思路，follow me!
2.1 定义全局变量
结果列表res和这道题核心函数返回值对应, 是二维列表。
一维列表path对应于二维列表中的每一个一维列表元素元素。
sum则是记录了path里面的节点值总和, 在后续进行操作的时候必须保持同步！
// 需要返回的结果列表
public static List<List<Integer>> res;
// 记录每一条路径
public static List<Integer> path;
// 和path对应, 记录单条路径path里面的节点值的总和
public static int sum;
// 懒得传递参数, 设置为全局变量
public static int target;记得初始化变量：
public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
res = new LinkedList<>();
path = new LinkedList<>();
target = targetSum;
dfs(root);
return res;
}2.2 思路模拟
2.2.1 访问节点操作
每当访问了一个节点, 将其值加入进临时的路径path以及path元素值计数器sum。
注意他们是绑定操作嗷, 穿一条裤子的, 我们意念合一！
sum += root.val;
path.add(root.val);2.2.2 何时更新结果列表res
当到了最深处叶子节点, 同时从根节点到叶子节点的临时路径path里面的节点值总和sum和目标值targetSum一致。
比如对于path：5->4->11->2这一条链路, sum为22, 和target一致！
此处我扔了提莫的蘑菇, 待会爆炸, 请见后续。
if(root.left == null && root.right == null && sum == target){
res.add(new LinkedList<>(path));
}2.2.3 继续深入
当判断并处理完这个节点之后, 比如节点11, 此时没有到叶子节点, 同时里面的sum为20, 不等于22。
此时就要继续深入, 对它的左右孩子进行递归：
dfs(root.left);
dfs(root.right);2.2.4 回溯
和2.2.1小节：访问节点对应
原先是加, 现在则是减, 同样是绑定操作path和sum。
此时dfs函数走到了最后, 自动完成回溯。
如果当前节点是上一个节点的左孩子, 对于上一个节点的dfs, 此时的操作是dfs(root.right);
如果当前节点是上一个节点的右孩子, 对于上一个节点的dfs, 此时的操作则又是回溯, 继续回溯到再上面一层, 以此类推。
sum -= root.val;
path.remove(path.size()-1);2.2.5 判空
当踩空了怎么办, 遇到了空节点, 直接返回！
判空只有两个地方能遇到,
- 一开始访问这整棵树的根节点的时候, 根节点为空, 直接游戏失败；
- 访问完了叶子节点之后, 同时此时拥有的积分sum不等于目标值targetSum, 还要遍历叶子节点的左右两个子节点, 但是两孩子都为空, 此时刚dfs进去, 游戏还没开始就结束了。
if(root == null) return;2.2.6 代码
先贴个代码：
main()函数中的内容见第3节。
public class Leetcode_113_PathSum2 {
// 需要返回的结果列表
public static List<List<Integer>> res;
// 记录每一条路径
public static List<Integer> path;
// 和path对应, 记录单条路径path里面的节点值的总和
public static int sum;
// 懒得传递参数, 设置为全局变量
public static int target;
public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
res = new LinkedList<>();
path = new LinkedList<>();
target = targetSum;
dfs(root);
return res;
}
public static void dfs(TreeNode root){
// 遇到空节点, 返回--->第一次访问的根节点或者是叶子节点的孩子为空 return
if(root == null) return;
// 处理当前节点
sum += root.val;
path.add(root.val);
// 当这条路径总和为target, 同时当前节点是叶子节点 加入进去结果列表
if(root.left == null && root.right == null && sum == target){
res.add(path);
}
// 继续递归当前节点的左右子节点
dfs(root.left);
dfs(root.right);
// 回溯 注意绑定操作
sum -= root.val;
path.remove(path.size()-1);
}
public static void main(String[] args) {
// 1. 获取打印工具对象, 第二个参数为0代表链表工具, 为1代表二叉树工具
PrintUtils utils = new PrintUtils(new int[]{5, 4, 8, 11, Constant.NULL, 13, 4, 7, 2, Constant.NULL, Constant.NULL, 5, 1}, 1);
// 2. 自动根据工具对象类型为链表还是二叉树, 打印出对应的结构到控制台
utils.print();
// 3. 获取二叉树结构对象, 作为这道题的参数传递
TreeNode root = utils.getTreeNode();
System.out.println(pathSum(root, 22));
}
}3. 结果演示[分享打印工具类]
同样地, 在力扣的核心函数中, 需要传递的参数是TreeNode类型, 此时出了问题也不好判断,
如果你想在本地IDEA里面看, 还有手动构造二叉树结构, 类似于：
// 慢慢构造树节点
TreeNode node1 = new TreeNode(5);
TreeNode node2 = new TreeNode(4);
TreeNode node3 = new TreeNode(8);
TreeNode node4 = new TreeNode(11);
TreeNode node5 = new TreeNode(13);
TreeNode node6 = new TreeNode(4);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(2);
TreeNode node9 = new TreeNode(1);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node3.left = node5;
node3.right = node6;
node4.left = node7;
node4.right = node8;
node6.right = node9;
// 传入本题参数
System.out.println(pathSum(root, 22));
为各位大懒猪们推荐我写的垃圾工具类, 可以轻松通过数组构造树或者链表结构
其中的Constant.NULL赋值为Integer.MIN_VALUE, 作为二叉树中的空节点：
public static void main(String[] args) {
// 1. 获取打印工具对象, 第二个参数为0代表链表工具, 为1代表二叉树工具
PrintUtils utils = new PrintUtils(new int[]{5, 4, 8, 11, Constant.NULL, 13, 4, 7, 2, Constant.NULL, Constant.NULL, 5, 1}, 1);
// 2. 自动根据工具对象类型为链表还是二叉树, 打印出对应的结构到控制台
utils.print();
// 3. 获取二叉树结构对象, 作为这道题的参数传递
TreeNode root = utils.getTreeNode();
System.out.println(pathSum(root, 22));
}我们打印出来看看：
控制台：
卧槽, 怎么结果列表res没有值啊。
3.1 问题排查
我们来debug一下：先打断点
我们直接到第一个成功完成目标的叶子节点2：
此时的path和sum都是正确的，并且能够成功将这条path加入进去res:
那我们继续下一步：兄弟们可以跟着我一起来：
在处理完节点2, 并且已经访问完了叶子节点2的左右空节点, 接下来将会回溯到它的父节点11。
此时的path和sum也是完全没有问题的。
那往上面看看结果列表res呢？
我去, 结果列表刚刚不还是[5->4->11->2]吗, 怎么path删除了最后一个节点之后, res里面的列表也变了啊？
让我们思考一下，嗷嗷嗷啊,
一维列表path是一个可变对象LinkedList, 我们每次加入进去res的时候：
实际上只是把同一个path对象的引用存进了 res 里，并没有复制一份新的列表。
此时想起我2.2.2小节埋的蘑菇了吗?
res.add(path);那我们改写一下，
将path放进去新new出来的列表里面：
res.add(new LinkedList<>(path));重新运行：
3.2 提交
复制到leetcode提交：过啦！
4. 完整代码
Java：
public class Leetcode_113_PathSum2 {
// 需要返回的结果列表
public static List<List<Integer>> res;
// 记录每一条路径
public static List<Integer> path;
// 和path对应, 记录单条路径path里面的节点值的总和
public static int sum;
// 懒得传递参数, 设置为全局变量
public static int target;
public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
res = new LinkedList<>();
path = new LinkedList<>();
target = targetSum;
dfs(root);
return res;
}
public static void dfs(TreeNode root){
// 遇到空节点, 返回--->第一次访问的根节点或者是叶子节点的孩子为空 return
if(root == null) return;
// 处理当前节点
sum += root.val;
path.add(root.val);
// 当这条路径总和为target, 同时当前节点是叶子节点 加入进去结果列表
if(root.left == null && root.right == null && sum == target){
// 必须将path放进重新new出来的列表里面
res.add(new LinkedList<>(path));
}
// 继续递归当前节点的左右子节点
dfs(root.left);
dfs(root.right);
// 回溯 注意绑定操作
sum -= root.val;
path.remove(path.size()-1);
}
public static void main(String[] args) {
// 1. 获取打印工具对象, 第二个参数为0代表链表工具, 为1代表二叉树工具
PrintUtils utils = new PrintUtils(new int[]{5, 4, 8, 11, Constant.NULL, 13, 4, 7, 2, Constant.NULL, Constant.NULL, 5, 1}, 1);
// 2. 自动根据工具对象类型为链表还是二叉树, 打印出对应的结构到控制台
utils.print();
// 3. 获取二叉树结构对象, 作为这道题的参数传递
TreeNode root = utils.getTreeNode();
System.out.println(pathSum(root, 22));
}
}C++：
class Leetcode_113_PathSum2 {
public:
// 需要返回的结果列表
static vector<vector<int>> res;
// 记录每一条路径
static vector<int> path;
// 和path对应, 记录单条路径path里面的节点值的总和
static int sum;
// 懒得传递参数, 设置为全局变量
static int target;
static vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
res.clear();
path.clear();
target = targetSum;
dfs(root);
return res;
}
private:
static void dfs(TreeNode* root) {
// 遇到空节点, 返回--->第一次访问的根节点或者是叶子节点的孩子为空 return
if (root == nullptr) return;
// 处理当前节点
sum += root->val;
path.push_back(root->val);
// 当这条路径总和为target, 同时当前节点是叶子节点 加入进去结果列表
if (root->left == nullptr && root->right == nullptr && sum == target) {
// 必须将path放进重新new出来的列表里面
res.push_back(vector<int>(path));
}
// 继续递归当前节点的左右子节点
dfs(root->left);
dfs(root->right);
// 回溯 注意绑定操作
sum -= root->val;
path.pop_back();
}
};
// 静态成员定义
vector<vector<int>> Leetcode_113_PathSum2::res;
vector<int> Leetcode_113_PathSum2::path;
int Leetcode_113_PathSum2::sum = 0;
int Leetcode_113_PathSum2::target = 0;JS：
// 需要返回的结果列表
let res;
// 记录每一条路径
let path;
// 和path对应, 记录单条路径path里面的节点值的总和
let sum;
// 懒得传递参数, 设置为全局变量
let target;
const pathSum = function(root, targetSum) {
res = [];
path = [];
target = targetSum;
sum = 0;
dfs(root);
return res;
};
function dfs(root) {
// 遇到空节点, 返回--->第一次访问的根节点或者是叶子节点的孩子为空 return
if (root === null) return;
// 处理当前节点
sum += root.val;
path.push(root.val);
// 当这条路径总和为target, 同时当前节点是叶子节点 加入进去结果列表
if (root.left === null && root.right === null && sum === target) {
// 必须将path放进重新new出来的列表里面
res.push([...path]);
}
// 继续递归当前节点的左右子节点
dfs(root.left);
dfs(root.right);
// 回溯 注意绑定操作
sum -= root.val;
path.pop();
}5. 一键三连么么哒
感谢你看完这篇算法分享博客,
宝宝们觉得我的屎山代码能提供帮助的话, 点赞收藏么么哒。
说, 我会守护Java的一切, 重铸Java荣光, 我辈义不容辞！
不定期分享学习笔记么么哒(｡･ω･｡)ﾉ♡
期待下一篇更新的话，可以订阅专栏并点点关注mua!, 及时让宝宝们看到。
扫一扫
615
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
