「剑指 Offer 34. 二叉树中和为某一值的路径」
力扣题目链接[1]
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 「从根节点到叶子节点」 路径总和等于给定目标和的路径。
「叶子节点」是指没有子节点的节点。
示例 1：
代码语言：javascript复制输入：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：
代码语言：javascript复制输入：root = [1,2,3], targetSum = 5
输出：[]
「提示：」
- 树中节点总数在范围
[0, 5000]内 1000 <= Node.val <= 10001000 <= targetSum <= 1000
思路：
根据题目要求，要寻找根节点到叶子节点匹配的路径，也就是说我们需要遍历二叉树。这里采取先序遍历，同时记录匹配的路径的方式。
所谓先序遍历，就是先获取根节点的值，然后递归获取左子节点，然后递归获取右子节点。
先来看最终的代码，然后具体分析：
先序遍历
代码语言：javascript复制/**
* @param {TreeNode} root
* @param {number} target
* @return {number[][]}
*/
const pathSum = (root, target) => {
let result = []; // 初始化结果数组
let path = []; // 初始化放置路径的数组
const recur = (root, target) => { // 递归函数
if (!root) return; // 递归终止条件
path.push(root.val) // 先序获取根节点的值，并放至路径数组中
target -= root.val; // 递减目标值，方便传入子节点递归
if (target === 0 && !root.left && !root.right) {
result.push([...path]); // 满足条件便放至结果数组
}
recur(root.left, target) // 递归左子节点
recur(root.right, target) // 递归右子节点
path.pop() // 回溯时弹出放入的值
}
recur(root, target) // 开始递归
return result; // 返回最终结果
};
- 「时间复杂度 O(n)」。
- 「空间复杂度 O(n)」。
分析：
既然是递归的进行先序遍历，那么重点就在于递归函数里的逻辑。在主函数中，我们声明了结果数组和存放路径的数组，调用递归函数并返回结果值。
进入到递归函数，首先不能忘记递归终止条件。当我们递归到叶子节点的子节点的时候，就需要直接返回。
然后将当前节点的值放入路径数组中，同时将传入的第二个参数进行递减。因为函数的传参是按值传递，所以不用担心会对调用栈其他函数造成影响。
此时需要判断是否符合条件，需要满足两个条件：
- 当前节点时叶子节点
- 当前的目标值已被递减为 0，说明路径数组中的值相加刚好等于主函数中的目标值
当满足条件时，就将路径数组进行浅拷贝，放至结果数组中。不能直接放至是因为数组是引用类型，必须拷贝一份副本才不会造成影响。
其实如果满足条件的话，意味着当前节点就是叶子节点，而叶子节点不存在子节点，在if判断里可以提前返回。如果不提前返回也可以，因为再次递归子节点会符合第一行代码，也会进行返回。
因此，不管当前节点是否有子节点，我们都可以进行递归左右子节点。
最后，回溯的时候需要将path中被添加的值弹出。因为我们只维护了一个路径数组，不弹出的话，会对其他分支造成影响。
总结
本题通过先序遍历进行题解。而先序、中序、后序遍历的区别也要掌握。本题需要注意的点就是路径数组，放至结果数组中需要浅拷贝，回溯的时候需要弹出遍历时添加的值。
复杂度方面，由于需要遍历二叉树所有的节点，因此时间复杂度是O(n) 。最坏情况下，当二叉树退化为链表时，需要存储二叉树所有的节点，因此空间复杂度是O(n) 。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dy6pt/
