难度中等919
给你二叉树的根节点 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
递归法
因为这道题的迭代法比较复杂，所以并没有必要去实现，这里只讲递归法！
因为我们需要遍历全部的路径，所以我们的子函数递归不使用返回值，并且我们这里利用了 targetSum 减法的方式来判断叶子节点的时候是否满足路径的和！这个可以参考 路径总和Ⅰ 的题解！
💥💥💥最重要的步骤就是回溯的时候要记得将我们的 v 数组一个一个的 pop 掉不符合的路径上的值！
class Solution {
public:
void path(TreeNode* root, vector<vector<int>>& vv, vector<int>& v, int targetSum)
{
if(root == nullptr)
return;
// 利用减法每次让targetSum减去当前节点值，并且尾插当前节点值到v中
targetSum -= root->val;
v.push_back(root->val);
// 若为叶子节点并且targetSum减到为0，说明符合，则更新vv
if(root->left == nullptr && root->right == nullptr && targetSum == 0)
vv.push_back(v);
// 继续递归左右子树查找其它路径
path(root->left, vv, v, targetSum);
path(root->right, vv, v, targetSum);
// 最后别忘了要将不符合路径的值一个一个回溯过程中pop掉
v.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> vv;
vector<int> v;
path(root, vv, v, targetSum);
return vv;
}
};