题目
给你二叉树的根节点 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
解答
本题可以使用深度优先搜索（DFS）求解。从根节点开始，依次搜索左子树和右子树，直到找到符合条件的路径。具体来说，我们可以使用递归的方式，每次遍历到一个节点时，将该节点加入路径中，并更新目标值。如果该节点是叶子节点，且目标值为 0，则说明找到了一条符合条件的路径，将该路径加入结果数组中。否则，继续搜索左子树和右子树。在搜索之后，需要将当前节点从路径中删除，以便回溯到之前的状态。C++代码实现如下：
/**
* 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:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res;
vector<int> path;
dfs(root, targetSum, res, path);
return res;
}
void dfs(TreeNode* node, int targetSum, vector<vector<int>>& res, vector<int>& path) {
if (!node) return; // 如果当前节点为空，则直接返回
path.push_back(node->val); // 将当前节点的值加入路径中
targetSum -= node->val; // 更新目标值
if (!node->left && !node->right && targetSum == 0) { // 如果当前节点是叶子节点，且目标值为 0，则说明找到了一条符合条件的路径
res.push_back(path); // 将该路径加入结果数组
} else {
dfs(node->left, targetSum, res, path); // 搜索左子树
dfs(node->right, targetSum, res, path); // 搜索右子树
}
path.pop_back(); // 回溯：将当前节点从路径中删除，恢复到搜索之前的状态
}
};
path.pop_back()是 C++ 中 vector 容器的成员函数，用于删除 vector 容器中的最后一个元素。在本题中，由于我们在搜索过程中需要记录搜索路径，因此使用了一个path数组来保存路径。在每次搜索到一个新节点时，我们将该节点的值加入path数组中，如果搜索结束后未找到符合条件的路径，需要将该节点从path数组中删除，回溯到之前的状态，继续搜索其他节点。因此，在代码中，path.pop_back()的作用是删除path数组中最后一个元素，以便回溯到之前的状态。
时间复杂度分析：
本题的时间复杂度为$ O(N^2)$，其中 N 表示二叉树的节点数。在最坏情况下，二叉树的形态类似于一个单链表，此时需要遍历所有节点，时间复杂度为 $O(N)$。对于每个节点，由于需要将该节点加入路径中，时间复杂度为$ O(N)$，因此总时间复杂度为 $O(N^2)$。
空间复杂度分析：
本题的空间复杂度为 $O(N)$，其中 N 表示二叉树的节点数。递归调用的栈空间最多为 $O(N)$，路径数组的空间为 $O(N)$，因此总空间复杂度为 $O(N)$。