leetcode算法（257.二叉树的所有路径） - 实践

二叉树递归（前序遍历）

1.递归函数参数以及返回值

要传入根节点，记录每一条路径的path，和存放结果集的result，这里递归不需要返回值，代码如下：

void traversal(TreeNode* cur, vector& path, vector& result)

2.确定递归终止条件

本题要找到叶子节点。那么什么时候算是找到了叶子节点？ 是当 cur不为空，其左右孩子都为空的时候，就找到叶子节点。

所以在本题的终止条件是：

if (cur->left == NULL && cur->right == NULL) {终止处理逻辑
}

使用vector<int> 结构path来记录路径，要把vector<int> 结构的path转为string格式，再把这个string 放进 result里。

终止处理逻辑如下：

if (cur->left == NULL && cur->right == NULL) { // 遇到叶子节点// 创建一个空字符串，用于存储最终的路径字符串string sPath;// 遍历path向量（存储了从根节点到当前叶子节点的所有节点值）// 循环到 path.size() - 1，即不包括最后一个元素// 因为每个元素后面需要添加"->"，但最后一个元素不需要for (int i = 0; i < path.size() - 1; i++) {// 将第i个节点的整数值转换为字符串并追加到sPathsPath += to_string(path[i]);// 在节点值后面添加箭头符号"->"，表示节点间的连接sPath += "->";}// 单独处理最后一个节点（即当前叶子节点）// 因为最后一个节点后面不需要添加"->"sPath += to_string(path[path.size() - 1]);// 将构建好的完整路径字符串添加到结果集result中result.push_back(sPath);// 返回上一层递归，因为叶子节点已经处理完毕return;
}

解释：

1. 条件判断：if (cur->left == NULL && cur->right == NULL)

   • 检查当前节点是否为叶子节点（没有左右子节点）

2. 创建字符串：string sPath;

   • 初始化一个空字符串，用于构建最终的路径字符串

3. 循环构建路径：for (int i = 0; i < path.size() - 1; i++)

   • path 是一个 vector<int>，存储了从根节点到当前节点的所有节点值

   • 循环遍历除了最后一个元素之外的所有元素

   • 对每个元素：先添加节点值，再添加 "->"

4. 添加最后一个节点：sPath += to_string(path[path.size() - 1]);

   • 单独处理最后一个元素（叶子节点）

   • 只添加节点值，不添加 "->"

5. 保存结果：result.push_back(sPath);

   • 将构建好的完整路径字符串添加到结果集中

6. 返回：return;

   • 结束当前递归分支，返回到上一层

本题的完整代码如下：

class Solution {
private:// 递归遍历函数// cur: 当前遍历的节点// path: 存储当前路径的节点值（引用传递，所有递归层共享）// result: 存储所有完整路径的结果集（引用传递）void traversal(TreeNode* cur, vector& path, vector& result) {// 先将当前节点的值添加到路径中// 这是"中"序遍历的一部分（前序处理）// 注释解释：为什么在这里添加？因为最后一个节点（叶子节点）也要加入pathpath.push_back(cur->val);// 检查当前节点是否为叶子节点（没有左右子节点）if (cur->left == NULL && cur->right == NULL) {// 如果是叶子节点，开始构建路径字符串string sPath; // 用于存储当前路径的字符串表示// 遍历path中除了最后一个元素之外的所有元素// 为每个元素添加值后加上"->"for (int i =