当前位置：首页 > news >正文

力扣第257题二叉树的所有路径 c++ 树深度优先搜索字符串回溯二叉树

news 2025/6/29 2:32:10

题目

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 关键字，它更为直观和安全。