大家好，我是吴师兄。
小伙伴们在平时的开发过程中，都经历过这种情况吧：别人的代码运行好好的，自己 CV 过来却发现有问题，折腾了半天最后发现问题出在少数几行代码上。
在算法刷题的过程中，就有不少题目是这样的，明明思路很好想，代码也很好写，但就是提交不通过，问题就出在一两行代码上，而这一两行代码短则卡半小时，长则卡几天。
比如下面这道算法题，不难，代码很好写，但如果对于对象的浅拷贝和深拷贝这个知识点不熟练的话，十有八九会写错。
那么来看题目描述：
给你二叉树的根节点 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]]
先来理解题意。
对于一棵二叉树来说，它有很多个叶子节点，那么从根节点开始出发，到这些叶子节点就会有很多种路径，每一条路径上面的节点值累加起来会有一个值 sum，题目需要我们找出 sum 等于目标值 target 的那些路径。
由此我们可以发现，整个过程就是一个不断深度遍历搜索到叶子节点的过程，一旦发现到某个叶子节点时，需要判断一下这条路径上的节点和是否和 target 相同，如果不同，需要去搜索其它的路径？
那么怎么去搜索其它的路径呢？
从当前叶子节点返回到它的父节点！
这个过程就是回溯的过程，因此我们需要保存之前的状态。
用什么数据结构保存呢？
栈！
每次遍历到一个新节点时，都把当前节点加入到一个栈中，如果需要返回到它的父节点，那么只需要把栈中的栈顶元素弹出即可。
理解清楚这些关键信息之后，来看一下具体操作：
1、构建一个 value，用来计算当前路径下节点的总和
2、构建一个 path，用来记录满足条件的路径
3、构建一个栈，用来保存当前路径下的节点
4、 从根节点开始搜索
5、在搜索过程中，一直搜索到叶子节点
- 1、把当前的节点值添加到栈中，栈中保存的就是从根节点到当前节点的路径
- 2、将当前访问节点的值累加到 value 上
6、如果搜索到了叶子节点，判断一下 value 是否和目标值 target 相同
- 1、如果相同，找到一条路径，把这条路径添加到 path 中
- 2、如果不相同，需要从当前叶子节点返回到它的父节点，返回的方式是将该节点从栈中弹出，那么栈顶元素就是父节点了；同时，记得在 value 上减去该节点的值
看到这里，代码已经很好写了，但问题会出在记录路径这一步。
如果没注意值类型和引用类型的区别，或者忽略了浅拷贝和深拷贝的概念，一开始写出的代码基本上都是直接 path.append(stack)。
有不少人都曾经卡在这里，被折磨半小时。
如果注意到了这个问题，那么实际上代码就挺好写。
代码语言：javascript复制// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
// 构建一个 value，用来计算当前路径下节点的总和
int value = 0;
// 构建一个 path，用来记录满足条件的路径
List<List<Integer>> path = new LinkedList<>();
// 构建一个栈，用来保存当前路径下的节点
Stack<Integer> stack = new Stack<>();
// 从根节点开始搜索
search(root,value,targetSum,stack,path);
// 返回满足条件的路径
return path;
}
// node 为正在遍历的节点
// value 为栈中各个节点值的总和
// targetSum 为目标路径的和
// stack 存储该路径上的所有节点
// path 存储满足条件，即路径上的各个节点之和为 targetSum 的那些路径
private void search(TreeNode node,int value,int targetSum ,Stack<Integer> stack,List<List<Integer>> path){
// 如果节点为空，那么就不需要再访问下去了
if(node == null) return;
// 将当前访问节点的值累加到 value 上
value = node.val;
// 把当前的节点值添加到栈中，栈中保存的就是从根节点到当前节点的路径
stack.push(node.val);
// 如果当前节点的左子树为空
// 并且当前节点的右子树也为空
// 即当前节点为叶子节点
// 同时当前路径下的节点值之和 value 与目标值 targetSum 相等
// 说明找到了一条符合条件的路径
if(node.left == null && node.right == null && value == targetSum){
// 把这条路径添加到 path 中
path.add(new LinkedList<>(stack));
}
// 继续递归的搜索当前节点 node 的左子树
search(node.left,value,targetSum,stack,path);
// 继续递归的搜索当前节点 node 的右子树
search(node.right,value,targetSum,stack,path);
// 搜索完当前节点的左右子树之后，当前节点已经完成了访问，需要返回到它的父节点
// 所以 value 减去当前节点的值
value -= node.val;
// 栈也弹出当前的节点值
stack.pop();
}
}
是不是很简单，注意细节的话，五分钟又学会了一道算法题。
