二叉树的所有路径（dfs）1

题目描述： 给定一个二叉树，任务是返回所有从根节点到叶子节点的路径。叶子节点是指没有子节点的节点。例如，给定如下的二叉树： ``` 1 / \ 2 3 \ 5 ``` 应该返回的路径包括 "1->2->5" 和 "1->3"。 解题思路： 这是一个典型的深度优先搜索（DFS）问题，可以使用递归的方法来解决。我们需要遍历整个二叉树，从根节点开始，每次到达一个节点时，将其值添加到当前路径中。当到达叶子节点时，将当前路径加入结果列表。如果节点不是叶子节点，那么继续遍历其左子树和右子树。 代码解析： ```cpp // 定义二叉树节点结构体 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: // 使用DFS方法遍历二叉树并收集路径 void dfs(TreeNode* root, string path, vector<string>& res) { if (root == nullptr) return; path += to_string(root->val); // 将当前节点值添加到路径字符串 if (root->left == nullptr && root->right == nullptr) { res.push_back(path); // 如果是叶子节点，将路径添加到结果列表 } else { path += "->"; // 非叶子节点，路径加上分隔符 dfs(root->left, path, res); // 递归遍历左子树 dfs(root->right, path, res); // 递归遍历右子树 } } // 主函数，调用dfs并返回结果 vector<string> binaryTreePaths(TreeNode* root) { string str = ""; // 初始化路径字符串 vector<string> res; // 结果列表 dfs(root, str, res); // 从根节点开始遍历 return res; // 返回所有路径 } }; ``` 在`dfs`函数中，我们首先检查当前节点是否为空，如果为空则直接返回。接着，我们将当前节点的值拼接到路径字符串中。然后，我们检查当前节点是否为叶子节点，如果是，则将路径添加到结果列表`res`中。如果不是叶子节点，我们继续递归地遍历左子树和右子树，并在路径字符串中添加分隔符 "->"。 在`binaryTreePaths`主函数中，我们初始化路径字符串`str`为空，结果列表`res`也为空。然后，我们调用`dfs`函数，从根节点开始遍历，最后返回所有找到的路径。 这个解决方案的时间复杂度是O(N)，其中N是二叉树的节点数量，因为每个节点都会被访问一次。空间复杂度是O(M)，其中M是结果路径字符串的总长度，因为每个路径都需要存储在结果列表中。在最坏的情况下，二叉树可能是一条链，此时M等于N。