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

17网站一起做网店潮汕依依北京网站seo招聘

17网站一起做网店潮汕依依,北京网站seo招聘,什么是h5宣传,企业建设营销型网站步骤题目 中等 提示 给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同…

题目

中等

提示

给你二叉树的根结点 root ,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1:

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [0]
输出:[0]

提示:

  • 树中结点数在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

进阶:你可以使用原地算法(O(1) 额外空间)展开这棵树吗?


面试中遇到过这道题?

1/5

通过次数

465.3K

提交次数

631.8K

通过率

73.6%

结点结构

/*** Definition for a binary tree node.* 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:void preorder(TreeNode *root,vector<TreeNode*> &temp){if(!root) return ;temp.push_back(root);preorder(root->left,temp);preorder(root->right,temp);}void flatten(TreeNode* root) {if(!root) return;vector<TreeNode*> temp;preorder(root,temp);temp.push_back(NULL);for(int i=0;i<temp.size()-1;i++){temp[i]->left=NULL;temp[i]->right=temp[i+1];}}
};

官解还提供了下面两种方法

方法二:前序遍历和展开同时进行

使用方法一的前序遍历,由于将节点展开之后会破坏二叉树的结构而丢失子节点的信息,因此前序遍历和展开为单链表分成了两步。能不能在不丢失子节点的信息的情况下,将前序遍历和展开为单链表同时进行?

之所以会在破坏二叉树的结构之后丢失子节点的信息,是因为在对左子树进行遍历时,没有存储右子节点的信息,在遍历完左子树之后才获得右子节点的信息。只要对前序遍历进行修改,在遍历左子树之前就获得左右子节点的信息,并存入栈内,子节点的信息就不会丢失,就可以将前序遍历和展开为单链表同时进行。

该做法不适用于递归实现的前序遍历,只适用于迭代实现的前序遍历。修改后的前序遍历的具体做法是,每次从栈内弹出一个节点作为当前访问的节点,获得该节点的子节点,如果子节点不为空,则依次将右子节点和左子节点压入栈内(注意入栈顺序)。

展开为单链表的做法是,维护上一个访问的节点 prev,每次访问一个节点时,令当前访问的节点为 curr,将 prev 的左子节点设为 null 以及将 prev 的右子节点设为 curr,然后将 curr 赋值给 prev,进入下一个节点的访问,直到遍历结束。需要注意的是,初始时 prev 为 null,只有在 prev 不为 null 时才能对 prev 的左右子节点进行更新。

class Solution {
public:void flatten(TreeNode* root) {if (root == nullptr) {return;}auto stk = stack<TreeNode*>();stk.push(root);TreeNode *prev = nullptr;while (!stk.empty()) {TreeNode *curr = stk.top(); stk.pop();if (prev != nullptr) {prev->left = nullptr;prev->right = curr;}TreeNode *left = curr->left, *right = curr->right;if (right != nullptr) {stk.push(right);}if (left != nullptr) {stk.push(left);}prev = curr;}}
};

方法三:寻找前驱结点。(类似于Morris遍历)

前两种方法都借助前序遍历,前序遍历过程中需要使用栈存储节点。有没有空间复杂度是 O(1)O(1)O(1) 的做法呢?

注意到前序遍历访问各节点的顺序是根节点、左子树、右子树。如果一个节点的左子节点为空,则该节点不需要进行展开操作。如果一个节点的左子节点不为空,则该节点的左子树中的最后一个节点被访问之后,该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点,也是该节点的前驱节点。因此,问题转化成寻找当前节点的前驱节点。

具体做法是,对于当前节点,如果其左子节点不为空,则在其左子树中找到最右边的节点,作为前驱节点,将当前节点的右子节点赋给前驱节点的右子节点,然后将当前节点的左子节点赋给当前节点的右子节点,并将当前节点的左子节点设为空。对当前节点处理结束后,继续处理链表中的下一个节点,直到所有节点都处理结束。

class Solution {
public:void flatten(TreeNode* root) {TreeNode *curr = root;while (curr != nullptr) {if (curr->left != nullptr) {auto next = curr->left;auto predecessor = next;while (predecessor->right != nullptr) {predecessor = predecessor->right;}predecessor->right = curr->right;curr->left = nullptr;curr->right = next;}curr = curr->right;}}
};

http://www.dt0577.cn/news/7785.html

相关文章:

  • 如何建设社区网站首页在百度上怎么卖自己的产品
  • 上海专业做网站公司武汉网站建设推广公司
  • 沈阳做网站哪家最便宜微信小程序开发文档
  • 祥云平台做的网站效果好网络搭建教程
  • 深圳市网站建设公司百度seo网站优化
  • 页面设计属于什么专业seo网络排名优化
  • 用node和vue做的网站百度推广的四种收费形式
  • 基于dijango的网站开发优化方案
  • 动态网站开发 教材手游推广渠道和推广方式
  • 遨翔网站建设今日头条官网首页
  • 本网站维护升级德阳seo
  • 网站修改建设网络广告的收费模式有哪些
  • wordpress 照片墙 插件想找搜索引擎优化
  • 成都网站建设 天空在线十大推广app平台
  • 商业网站排名长春网站建设设计
  • 合肥有哪些做网站的公司域名查询ip爱站网
  • ipc网站备案查询亚马逊提升关键词排名的方法
  • 有没有专门做批发的网站最新新闻事件摘抄
  • 自己做网站要会什么软件网站优化seo培
  • 私人承接做网站多少钱搜狗优化排名
  • 怎么做网站动态地图迅雷磁力
  • 网站开发团队职能没有限制的国外搜索引擎
  • 做购物网站的引言怎么办网站平台
  • 住房和城乡建设部网站施工员成都网络推广
  • 重庆公司网站设计制作裂变营销五种模式十六种方法
  • led外贸网站制作永久免费域名申请
  • 做网站被抓网站搜索排优化怎么做
  • wordpress中文cms主题模板seo网页优化服务
  • 南阳网站优化费用口碑营销案例有哪些
  • 自己电脑做网站教程济源新站seo关键词排名推广