cf 14249（题目小凯的烦恼）

小凯的烦恼——解决CF 14249题目的方法

小凯是一名热爱编程的学生，最近他在做CF 14249题目时遇到了困难，不知道该如何下手。这让他非常烦恼。经过一番探索和尝试，小凯终于找到了解决这道题目的方法。下面，我们就来看看小凯是如何解决这个问题的。

题目背景

CF 14249题目是一道关于二叉树的问题，题目要求给定一棵二叉树，求出所有从根节点到叶子节点的路径中，权值和等于给定值的路径。这是一道比较典型的深度优先搜索（DFS）问题。

解题思路

对于这道题目，我们可以采用递归的方式来解决。具体来说，我们可以定义一个递归函数，该函数的参数包括当前节点、当前路径以及目标值。在递归过程中，我们需要判断当前节点是否为叶子节点，如果是叶子节点，则需要判断当前路径是否满足要求，如果满足要求，则将当前路径加入结果集中。如果当前节点不是叶子节点，则需要继续递归遍历其左右子树。

代码实现

下面是小凯实现该题目的代码：

```

void dfs(TreeNode* root, int sum, vector& path, vector>& res) {

if (!root) return;

path.push_back(root->val);

if (!root->left && !root->right) {

if (sum == root->val) {

res.push_back(path);

}

} else {

dfs(root->left, sum - root->val, path, res);

dfs(root->right, sum - root->val, path, res);

}

path.pop_back();

}

vector> pathSum(TreeNode* root, int sum) {

vector> res;

vector path;

dfs(root, sum, path, res);

return res;

}

```

代码解析

上面的代码中，我们定义了一个递归函数dfs，该函数的参数包括当前节点、当前路径以及目标值。在递归过程中，我们首先将当前节点的值加入路径中，然后判断当前节点是否为叶子节点。如果是叶子节点，则需要判断当前路径是否满足要求，如果满足要求，则将当前路径加入结果集中。如果当前节点不是叶子节点，则需要继续递归遍历其左右子树。

在代码实现中，我们使用了vector来存储当前路径和结果集。具体来说，我们在dfs函数中定义了一个vector类型的path变量，用于存储当前路径，以及一个vector>类型的res变量，用于存储结果集。在递归过程中，我们将当前节点的值加入path中，然后判断当前节点是否为叶子节点。如果是叶子节点，则需要判断当前路径是否满足要求，如果满足要求，则将当前路径加入res中。如果当前节点不是叶子节点，则需要继续递归遍历其左右子树。在递归结束后，我们需要将path中的最后一个元素弹出，以便回溯到上一层。