难度中等390
给你二叉树的根节点 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 题相同：https://leetcode-cn.com/problems/path-sum-ii/
先序遍历+记录路径
这道题因为要记录原来走过的路径，所以要用一个额外的空间 path 来存储对应的先走过的路径，结合先序遍历的原理，每次用 sum 记录这条路径的值的和，一旦遇到 sum 累加到了 target 大小，那么我们就判断一下题目的要求，也就是这个最后的点是否为叶子节点，是的话就将这条路径加入 vv 中！
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 注意path不传引用接收，因为我们不希望其不同路径会相互影响
void getPath(TreeNode* root, int target, vector<vector<int>>& vv, vector<int> path, int sum)
{
if(root == nullptr)
return;
sum += root->val;
path.push_back(root->val);
// 注意题目要求是叶子节点才加入最后的路径
if(sum == target && root->left == nullptr && root->right == nullptr)
{
vv.push_back(path);
return; // 直接return，因为这个路径下面再加上值的话就比target大了，不可能存在其它路径
}
getPath(root->left, target, vv, path, sum);
getPath(root->right, target, vv, path, sum);
}
vector<vector<int>> pathSum(TreeNode* root, int target) {
vector<vector<int>> vv;
vector<int> path; // 用于记录路径
int sum = 0;
getPath(root, target, vv, path, sum);
return vv;
}
};