装潢网站模板,温州app软件开发,网站开发制作公司有哪些,wordpress瀑布流模板题目
257. 二叉树的所有路径
简单
给你一个二叉树的根节点 root #xff0c;按 任意顺序 #xff0c;返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。 示例 1#xff1a; 输入#xff1a;root [1,2,3,null,5]
输出#xff1a;[1-2-按 任意顺序 返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。 示例 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-leftNULLnode-rightNULL如果是则将 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, vectorint path, vectorstring 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(); // 返回上一层递归之前弹出当前节点恢复路径状态}}vectorstring binaryTreePaths(TreeNode* root) {vectorint path; // 用于保存当前路径节点的值的数组vectorstring ans; // 用于保存所有路径字符串的数组if (root nullptr) return ans; // 特殊情况处理空树直接返回空结果数组traversal(root, path, ans); // 递归遍历二叉树找到所有路径return ans; // 返回结果数组}
};c优化代码 精简 class Solution {
public:// 辅助函数用于递归遍历二叉树并找到所有路径void traversal(TreeNode* node, string path, vectorstring 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);}vectorstring binaryTreePaths(TreeNode* root) {vectorstring ans; // 用于保存所有路径的数组traversal(root, , ans); // 递归遍历二叉树找到所有路径return ans; // 返回结果数组}
};对 traversal 函数进行了修改。我们使用一个额外的 string 类型的参数 path 来保存当前路径的字符串 而不是使用一个整数数组。在递归过程中我们将当前节点的值加入到 path 结尾并根据情况添加箭头符号 -。 此外我们还对参数进行了一些调整使用 nullptr 表示空指针而不是 NULL。这是 C11 引入的 nullptr 关键字它更为直观和安全。 觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
