四川和住房城乡建设厅网站logo图案素材免费网站
题目
257. 二叉树的所有路径
简单
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
思路和解题方法
1. 首先我们需要明确这个问题的目标，即找到所有从根节点到叶节点的路径。对于每一条路径，我们需要把其中的每个节点的值按顺序连接起来形成一个字符串，并将其保存在一个字符串数组中返回。
2. 通过观察代码，我们可以发现该题解中使用了递归的思想来解决问题。具体来说，它定义了一个名为
traversal的递归函数，该函数需要传入三个参数：
node: 当前访问的节点。path: 保存当前路径的节点值的数组。ans: 保存所有路径的字符串的数组。3. 对于每个节点
node，该函数首先将node->val添加到path中，并判断node是否为叶节点（即node->left==NULL&&node->right==NULL），如果是，则将path中的所有值按顺序连接起来形成一个字符串，并将其添加到ans数组中；否则，递归遍历node的左右子树，并在递归返回后将path数组中的最后一个元素弹出，以恢复到上一层递归时的状态。4. 最终，在主函数
binaryTreePaths中，我们首先判断根节点是否为空，如果为空，则返回空的字符串数组；否则，我们调用traversal函数，将根节点、空的path数组和空的ans数组作为参数传入，以获取所有路径。最后，返回ans数组即可。
复杂度
时间复杂度:
O(n)
时间复杂度：对于每个节点，我们只需要访问一次，其中 n 是节点数。
空间复杂度
O(n)
递归过程中使用了一个字符串类型的参数
path和一个字符串数组ans，以及递归调用栈，因此空间复杂度为 O(n)。特别地，如果所有的节点都在同一条路径上，递归栈的最大深度将是 n，在这种情况下，空间复杂度将达到 O(n) 的最坏情况。
c++ 代码
class Solution {
public:// 辅助函数，用于递归遍历二叉树并找到所有路径void traversal(TreeNode* node, vector<int>& path, vector<string>& ans) {// 将当前节点的值添加到路径中path.push_back(node->val);// 如果当前节点是叶节点，则将路径转化为字符串，并添加到结果数组中if (node->left == nullptr && node->right == nullptr) {string sPath; // 储存当前路径的字符串形式for (int i = 0; i < path.size() - 1; i++) {sPath += to_string(path[i]); // 将路径节点的值转化为字符串并添加到路径字符串中sPath += "->"; // 添加箭头符号分隔路径节点}sPath += to_string(path[path.size() - 1]); // 添加最后一个节点的值ans.push_back(sPath); // 将路径字符串添加到结果数组中return;}// 递归遍历左子树if (node->left) {traversal(node->left, path, ans);path.pop_back(); // 返回上一层递归之前，弹出当前节点，恢复路径状态}// 递归遍历右子树if (node->right) {traversal(node->right, path, ans);path.pop_back(); // 返回上一层递归之前，弹出当前节点，恢复路径状态}}vector<string> binaryTreePaths(TreeNode* root) {vector<int> path; // 用于保存当前路径节点的值的数组vector<string> ans; // 用于保存所有路径字符串的数组if (root == nullptr) return ans; // 特殊情况处理，空树直接返回空结果数组traversal(root, path, ans); // 递归遍历二叉树，找到所有路径return ans; // 返回结果数组}
};
c++优化代码 （精简）
class Solution {
public:// 辅助函数，用于递归遍历二叉树并找到所有路径void traversal(TreeNode* node, string path, vector<string>& ans) {// 如果节点为空，直接返回if (node == nullptr) return;// 将当前节点的值添加到路径中path += to_string(node->val);// 如果当前节点是叶节点，则将完整路径添加到结果数组中if (node->left == nullptr && node->right == nullptr) {ans.push_back(path);return;}// 添加箭头符号分隔路径节点path += "->";// 递归遍历左子树traversal(node->left, path, ans);// 递归遍历右子树traversal(node->right, path, ans);}vector<string> binaryTreePaths(TreeNode* root) {vector<string> ans; // 用于保存所有路径的数组traversal(root, "", ans); // 递归遍历二叉树，找到所有路径return ans; // 返回结果数组}
};
对
traversal函数进行了修改。我们使用一个额外的string类型的参数path来保存当前路径的字符串而不是使用一个整数数组。在递归过程中，我们将当前节点的值加入到
path结尾，并根据情况添加箭头符号"->"。此外，我们还对参数进行了一些调整，使用
nullptr表示空指针，而不是NULL。这是 C++11 引入的nullptr关键字，它更为直观和安全。
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。