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

个人网站域名怎么取公司页面设计

个人网站域名怎么取,公司页面设计,河北省建设工程信息网站,论证 政府门户网站建设代码思路 目标: 将二叉树展平(flatten)为一个单链表。展平后的链表应该按照前序遍历的顺序排列节点,即: • 节点的左子树指针设置为 nullptr。 • 节点的右子树指针指向下一个节点。 代码注释及思路 class Solution…

代码思路

目标:

将二叉树展平(flatten)为一个单链表。展平后的链表应该按照前序遍历的顺序排列节点,即:

• 节点的左子树指针设置为 nullptr。

• 节点的右子树指针指向下一个节点。

代码注释及思路


class Solution {public:// flatten函数:将二叉树转化为链表void flatten(TreeNode* root) {vector<TreeNode*> l; // 用来存储前序遍历的节点preorderTraversal(root, l);  // 先进行前序遍历并将节点加入到l中int n = l.size();  // 记录前序遍历中节点的个数// 连接所有节点,使其形成链表for (int i = 1; i < n; i++) {TreeNode *prev = l.at(i - 1), *curr = l.at(i);prev->left = nullptr;  // 将前一个节点的左指针置为NULLprev->right = curr;    // 将前一个节点的右指针指向当前节点}}// preorderTraversal函数:前序遍历二叉树,并将每个节点加入到vector l中void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {if (root != NULL) {  // 如果当前节点不为空l.push_back(root);  // 将当前节点加入到vector lpreorderTraversal(root->left, l);  // 递归遍历左子树preorderTraversal(root->right, l); // 递归遍历右子树}}};

l.at(i - 1) 和 l[i - 1] 在大多数情况下会表现得很相似,但它们有一些关键的区别,主要体现在安全性和异常处理上。

1. l.at(i - 1)

安全性:at() 是 std::vector 的一个成员函数,它会检查你传入的索引是否越界。如果索引超出了有效范围,它会抛出一个 std::out_of_range 异常。

行为:如果你访问了一个无效索引(比如负数或者超出了 vector 的大小),at() 会立即抛出异常,从而帮助你捕捉潜在的错误。

std::vector<int> v = {10, 20, 30, 40};

try {

    std::cout << v.at(5) << std::endl;  // 抛出 std::out_of_range 异常

} catch (const std::out_of_range& e) {

    std::cout << "Out of range: " << e.what() << std::endl;  // 会打印异常信息

}

2. l[i - 1]

安全性:operator[] 是 std::vector 的索引访问方式,它不会做越界检查。如果你使用一个无效的索引,它不会抛出异常,而是会产生未定义行为,可能导致程序崩溃、访问到非法内存等问题。

行为:即使访问了一个超出范围的索引,它也不会报错,而是直接返回一个非法的内存位置。

std::vector<int> v = {10, 20, 30, 40};

std::cout << v[5] << std::endl;  // 未定义行为,可能导致程序崩溃或异常

• at(i):比 operator[] 更安全,因为它会进行边界检查并抛出异常。

• operator[]:更加高效,因为没有进行边界检查,但使用不当会导致程序崩溃或产生不可预料的行为。

哪个更好?

• 如果你确定索引是有效的,或者你对代码的安全性非常关注,使用 operator[] 会更高效。

• 如果你更关心代码的安全性,尤其是在你不确定索引是否有效的情况下,使用 at() 更加可靠。

详细思路

1. 前序遍历

• 在 flatten 函数中,首先调用 preorderTraversal 对二叉树进行前序遍历。前序遍历的顺序是:根节点 → 左子树 → 右子树。

• 在 preorderTraversal 函数中,当访问一个节点时,将它加入到一个 vector<TreeNode*>(即 l)中。

• 递归进行左子树和右子树的遍历。

2. 重建链表

• 在完成前序遍历后,l 中存储了按前序遍历顺序排列的所有节点。

• 接下来,遍历这个 l,并对每一对相邻节点(prev 和 curr)做以下操作:

• 将 prev 节点的左指针置为 nullptr。

• 将 prev 节点的右指针指向 curr 节点。

• 这样,我们将树的结构变为链表,且节点按照前序遍历顺序排列。

运行步骤

假设输入的二叉树如下:

    1

   / \

  2   5

 / \   \

3   4   6

1. 调用 flatten(root),传入根节点 1。

2. 调用 preorderTraversal(root, l),此时开始前序遍历:

• l = [1](根节点 1)

• 遍历左子树,l = [1, 2]

• 遍历 2 的左子树,l = [1, 2, 3]

• 遍历 2 的右子树,l = [1, 2, 3, 4]

• 遍历右子树,l = [1, 2, 3, 4, 5]

• 遍历 5 的右子树,l = [1, 2, 3, 4, 5, 6]

3. 现在,l = [1, 2, 3, 4, 5, 6],即按前序遍历顺序排列的节点。

4. 接着,连接这些节点:

• prev = 1, curr = 2 → 1->left = nullptr, 1->right = 2

• prev = 2, curr = 3 → 2->left = nullptr, 2->right = 3

• prev = 3, curr = 4 → 3->left = nullptr, 3->right = 4

• prev = 4, curr = 5 → 4->left = nullptr, 4->right = 5

• prev = 5, curr = 6 → 5->left = nullptr, 5->right = 6

最终的链表结构如下:

1 -> 2 -> 3 -> 4 -> 5 -> 6

复杂度分析

时间复杂度:O(n),其中 n 是树中节点的数量。我们对树进行了一次前序遍历,遍历过程的时间复杂度是 O(n)。在重新连接节点时,也只需要遍历一次 l。

空间复杂度:O(n),主要是用于存储前序遍历结果的 vector l,其大小为 n。递归栈的深度是树的高度,最坏情况下是 O(n),最好的情况下是 O(log n)(如果树是平衡的)。

http://www.ds6.com.cn/news/17055.html

相关文章:

  • 长春火车站疫情防控最新政策百度建立自己的网站
  • 怎么做安居客网站seo外链技巧
  • 中国建设招聘信息网站百度搜索指数查询
  • 有没有做的很炫的科技型网站微信小程序开发工具
  • 建立网站目录结构时不正确的建议是网站发布与推广方案
  • 如何做网站青岛seo网站建设公司
  • 网站是做百度快照推广好广安seo外包
  • 强网站日常监测及内容建设百度app官方正式版
  • 免费 网站 cms营销网站建设门户
  • 网站收录突然全部没有了营销型网站推广
  • 哪个b2b网站做推广效果好网络推广的主要工作内容
  • 住房城乡建设委门户网站广州免费个人主页网站
  • 做网站的诈骗公司十大广告公司
  • 郑州网站设计网站网页设计案例
  • 云速建站可以建个人网站吗网站seo应用
  • 中山手机网站建设电话搜索引擎关键词快速优化
  • 家用电脑如何做网站服务器企业网站建设哪家好
  • 做网站用的什么服务器吗seo分析工具
  • 怎么样让网站做的大气百度seo查询系统
  • thinkphp做的网站怎么预览baidu百度首页官网
  • 江苏网站建设南通小红书seo排名帝搜软件
  • 程序开发语言有哪些上海seo优化
  • 泰安网站建设广告百度广告推广怎么做
  • 在线教育网站用什么做东莞网络推广平台
  • 做网站营业执照经营范围怎么填写北海seo快速排名
  • 喷码机营销型网站百度关键词优化首选667seo
  • Wordpress手机端模版性价比高seo排名优化的
  • 中山专业网站建设价格网页设计与制作学什么
  • 给博彩做网站网络销售的工作内容
  • 网站建设很难吗百度指数的搜索指数代表什么