题目链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/

1. 题目介绍（34. 二叉树中和为某一值的路径）

给你二叉树的根节点 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：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例3：

输入：root = [1,2], targetSum = 0
输出：[]

【条件约束】：

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

【相关题目】：

注意：本题与主站 113. 路径总和 II 题目相同。

2. 题解

2.1 递归（原书题解）-- O(n²)

时间复杂度O(n²)，空间复杂度O(n)

【解题思路】：

1. 使用前序遍历来遍历二叉树，当通过前序遍历的方式访问到某一个节点时，我们把该节点添加到路径上，并累加该节点的值。
2. 如果该节点为叶节点，并且路径中节点值的和刚好等于输入的整数，则当前路径符合要求，我们把它打印出来。
3. 如果当前节点不是叶节点，则继续访问它的子节点。
4. 当前节点访问结束后，递归方法将自动回到它的父节点。因此，我们在方法退出之前要在路径上删除当前节点并减去当前节点的值，以确保返回父节点时路径刚好是从根节点到父节点。
   ……

我们不难看出保存路径的数据结构实际上是一个栈，因为路径要与递归调用状态一致，而递归调用的本质就是一个压栈和出栈的过程。
……
【注意点】：

1. Stack的泛型直接定义为 Integer 即可，如果定义成 TreeNode ，为了返回结果，反而会需要额外定义List来存储单个路径。
2. 递归结束条件，一般情况下，递归需要由一个终止条件才行。但是下面解法中的递归会自动执行完毕，即遍历完所有节点，栈内元素会全部弹出完毕，执行终止，不存在无限循环的情况。
3. 将Stack类型转换为List类型：List list = new LinkedList<>(stack);
   更多内容可参考：【Java】stack转为list

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 解题思路：// 路径：由根节点到叶子节点所经过的所有节点共同组成// 叶子节点：是指没有子节点的节点// 定义返回列表List> list;public List> pathSum(TreeNode root, int targetSum) {// 判空if (root == null) return new ArrayList<>();// 定义栈来存储路径Stack path = new Stack<>();// 返回列表初始化list = new ArrayList<>();// 进入递归findPath(root, targetSum, path, 0);// 递归结束，返回结果return list;}public void findPath(TreeNode root, int targetSum, Stack path, int currSum){// 压入栈后，增加当前路径和currSum += root.val;// 从根节点出发，将根节点存入栈内path.push(root.val);// 递归结束条件，路径和符合条件，记录该路径// 1. 判断当前节点是否为叶子节点boolean isLeaf = (root.left == null) && (root.right == null);// 2. 路径和符合条件if ((currSum == targetSum) && isLeaf) {List row = new ArrayList<>(path);list.add(row);}// 遍历其子节点if (root.left != null) findPath(root.left, targetSum, path, currSum);if (root.right != null) findPath(root.right, targetSum, path, currSum);// 弹出节点path.pop();}
}

代码简化：

简化内容：

1. 递归函数的设计更加简洁，相较于原书题解中的四个参数，这里仅保留了用户需要输入的两个参数；
2. 确定符合条件的路径方法也更简洁，原书题解中是通过自己新定义的变量 currSum 根据遍历进行累加计算，直至等于 targetSum；而简化题解中，反其道而行之，直接对 targetSum 进行修改，直至其减到0，认为当前路径符合条件，可以保留；
3. 左、右子节点的递归没有设置判断条件，而是设置了递归结束条件 root == null (意为，当前节点为空时，结束当前递归)。
   ……

优化内容：

1. Stack换成了Deque，在力扣提交中提升了 1s 的效率：
   
   其原因在于：Stack 基于数组实现，LinkedList基于链表实现 （Deque是基于LinkedList实现的），数组随机访问效率高，但随机插入、随机删除效率低，链表与之相反。那么对于这道题，有频繁的插入、删除操作，那么我们利用LinkedList实现栈自然比Stack快很多了。
   ……
   更多内容可参考：
   [1] LeetCode刷题心得记录——为什么LinkedList比Stack效率要高？
   [2] JAVA 栈，为什么要使用Deque，而不推荐使用Stack
   [3] Java中的栈Stack、Deque、ArrayDeque、LinkedList
   [4] Java 容器源码分析之 Deque 与 ArrayDeque

class Solution {List> ret = new LinkedList>();// 优化：在这里LinkedList 要比 Stack 效率要高Deque path = new LinkedList();public List> pathSum(TreeNode root, int targetSum) {dfs(root, targetSum);return ret;}// 深度优先遍历// 简化1：设计的递归函数更加简洁，仅使用了两个参数public void dfs(TreeNode root, int targetSum) {if (root == null) {return;}path.offerLast(root.val);// 简化2：修改targetSum的值，减至0时，认为路径符合条件targetSum -= root.val;if (root.left == null && root.right == null && targetSum == 0) {ret.add(new LinkedList(path));}// 左子节点dfs(root.left, targetSum);// 右子节点dfs(root.right, targetSum);// 弹出/删除路径path.pollLast();}
}

2.2 广度优先搜索 – O(n²)

时间复杂度O(n²)，空间复杂度O(n)

用广度优先搜索的方式，遍历这棵树。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。
……
为了节省空间，我们使用哈希表记录树中的每一个节点的父节点。每次找到一个满足条件的节点，我们就从该节点出发不断向父节点迭代，即可还原出从根节点到当前节点的路径。
……
多少有点麻烦，不推荐.

class Solution {List> ret = new LinkedList>();Map map = new HashMap();public List> pathSum(TreeNode root, int target) {if (root == null) {return ret;}Queue queueNode = new LinkedList();Queue queueSum = new LinkedList();queueNode.offer(root);queueSum.offer(0);while (!queueNode.isEmpty()) {TreeNode node = queueNode.poll();int rec = queueSum.poll() + node.val;if (node.left == null && node.right == null) {if (rec == target) {getPath(node);}} else {if (node.left != null) {map.put(node.left, node);queueNode.offer(node.left);queueSum.offer(rec);}if (node.right != null) {map.put(node.right, node);queueNode.offer(node.right);queueSum.offer(rec);}}}return ret;}public void getPath(TreeNode node) {List temp = new LinkedList();while (node != null) {temp.add(node.val);node = map.get(node);}Collections.reverse(temp);ret.add(new LinkedList(temp));}
}

3. 参考资料

[1] 二叉树中和为某一值的路径 – 广度优先搜索方法 及 2.1 简化方法来源
[2] 面试题34. 二叉树中和为某一值的路径（回溯法，清晰图解）-- 图片来源