C++算法练习-day34——257.二叉树的所有路径

题目来源：. - 力扣（LeetCode）

题目思路分析

题目要求从给定的二叉树中找出所有从根节点到叶子节点的路径，并以字符串的形式返回这些路径。每条路径都应该表示为一个由箭头（->）分隔的节点值序列，从根节点到叶子节点。例如，对于以下二叉树：

    1  / \  2   3  \  5

所有根到叶子的路径为：["1->2->5", "1->3"]。

解题思路：

1. 使用深度优先搜索（DFS）遍历二叉树。
2. 从根节点开始，每次递归时将当前节点的值添加到路径字符串中。
3. 如果当前节点是叶子节点（即没有左右子节点），则将当前路径字符串添加到结果列表中。
4. 如果当前节点不是叶子节点，则继续递归遍历其左右子节点，并在路径字符串中添加箭头（->）作为分隔符。
5. 最终返回所有路径的列表。

代码:

#include <string>  
#include <vector>  
#include <sstream>  // 用于to_string  using namespace std;  // 二叉树节点的定义  
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:  // 递归函数，用于找出所有路径  void num_path(TreeNode* root, string path, vector<string>& paths) {  if (root) {  // 如果当前节点不为空  path += to_string(root->val);  // 将当前节点值添加到路径字符串中  if (!root->left && !root->right) {  // 如果当前节点是叶子节点  paths.push_back(path);  // 将路径添加到结果列表中  } else {  // 如果当前节点不是叶子节点  path += "->";  // 添加箭头作为分隔符  num_path(root->left, path, paths);  // 递归遍历左子节点  num_path(root->right, path, paths);  // 递归遍历右子节点  }  }  }  // 主函数，返回所有路径的列表  vector<string> binaryTreePaths(TreeNode* root) {  vector<string> paths;  // 用于存储所有路径的列表  num_path(root, "", paths);  // 从根节点开始，空字符串作为初始路径  return paths;  // 返回所有路径的列表  }  
};

知识点摘要

1. 二叉树：一种数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。
2. 深度优先搜索（DFS）：一种用于遍历或搜索树或图的算法，尽可能深的搜索树的分支。
3. 递归：一种在函数内部调用自身的编程技巧，常用于解决可以分解为相似子问题的问题。
4. 字符串操作：在C++中，使用std::string类进行字符串的拼接、转换等操作。
5. 向量（vector）：C++标准模板库（STL）中的一种动态数组，可以存储可变数量的元素。

通过这道题目，我们学习了如何使用深度优先搜索（DFS）和递归的方法来遍历二叉树，并找出所有从根节点到叶子节点的路径。在解决这个问题的过程中，我们使用了字符串来记录路径，并使用向量来存储所有路径。此外，我们还了解了C++中字符串和向量的基本操作。这个问题不仅考察了我们对二叉树的理解，还锻炼了我们使用递归和字符串操作的能力。希望这篇文章能帮助你更好地理解这个问题及其解决方案。