当前位置:网站首页>leetcode二叉搜索树与双向链表
leetcode二叉搜索树与双向链表
2022-08-09 18:52:00 【老鱼37】
思路:
1.创建一个新数组
2.中序遍历二叉树 将值放入数组里面
3.遍历数组将值放入双向链表中 建立双向关系
//链表题目已经给出,这里是为了给予展示
//创建一个链表
// struct TreeNode
// {
// int val;
// struct TreeNode*left;
// struct TreeNode*right;
// TreeNode(int x)
// {
// val=x;
// left=NULL;
// right=NULL;
// }
// };
class Solution {
public:
//创建一个数组
vector<TreeNode*>st;
void Inorder(TreeNode*root)
{
if(!root) return;
Inorder(root->left);
st.push_back(root);
Inorder(root->right);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
//中序遍历二叉树然后放入数组里面,然后遍历数组放入双向链表中
if(!pRootOfTree) return pRootOfTree;
Inorder(pRootOfTree);//中序遍历
//根据数组中的顺序将结点连接,注意i的范围
for(int i=0;i<st.size()-1;i++)
{
st[i]->right=st[i+1];//连接关系
st[i+1]->left=st[i];//连接关系
}
return st[0];
}
};
时间复杂度:O(N),等于中序遍历的时间复杂度。
空间复杂度:O(N),开辟了一个数组来存储结点。
解法二:
在树上动手脚,创建一个头指针,一个头指针的前一个指针
遍历左树,找到最左边的是树中最小的数,然后就是链表的头
遍历右树,找到最右边的是树中最大的数,然后就是链表的尾
然后依靠pre指针串联起来,最后输出链表头
class Solution {
public:
//返回的第一个指针,初值为最小值,为NUNLL
TreeNode*head=NULL;
//中序遍历当前值的上一位,初值为最小值,为NULL
TreeNode*pre=NULL;
TreeNode* Convert(TreeNode* pRootOfTree) {
if(pRootOfTree==NULL)
{
//中序递归
return NULL;
}
Convert(pRootOfTree->left);
//找到左树最左最小值
if(pre==NULL)
{
head=pRootOfTree;
pre=pRootOfTree;
}
else
{
pre->right=pRootOfTree;
pRootOfTree->left=pre;
pre=pRootOfTree;//pre等于新的root值
}
//遍历右树
Convert(pRootOfTree->right);
return head;
}
};
时间复杂度:O(N),等于中序遍历的时间复杂度。
空间复杂度:O(N),开辟了一个数组来存储结点。
如有错误,多多指教!
边栏推荐
猜你喜欢
ebook下载 | 《 企业高管IT战略指南——企业为何要落地DevOps》
IS31FL3737B general 12 x 12 LED drive 40 QFN I2C 42 ma
IS31FL3737B 通用12×12 LED驱动器 I2C 42mA 40QFN
Abbkine TraKine Pro 活细胞微管染色试剂盒重要特色
基于CC2530 E18-MS1-PCB Zigbee DIY作品
新出现的去中心化科学能够为科学领域带来什么?
[免费专栏] Android安全之APK动态方式逆向应用【三种Smali注入方法】
【kali-权限提升】(4.2.7)社会工程学工具包:权限维持创建后门、清除痕迹
[免费专栏] Android安全之Xposed插件开发【从零手把手带】教程
ebook download | "Business executives' IT strategy guide - why enterprises should implement DevOps"
随机推荐
基于CC2530 E18-MS1-PCB Zigbee DIY作品
如何抑制告警风暴?
视频是主动学习吗?
渗透测试-对新型内存马webshell的研究
AWS CodePipeLine 跨账号部署ECS
[免费专栏] Android安全之Android工程模式
MYSQL物理存储文件的页和INNOBUF的页是否有大小区别?
最新BEV感知基线 | 你确定需要激光雷达?(卡内基梅隆大学)
uniapp离线推送华为厂商申请流程
AWS CodePipeLine deploys ECS across accounts
Intensive reading of the paper: VIT - AN IMAGE IS WORTH 16X16 WORDS: TRANSFORMERS FOR IMAGE RECOGNITION AT SCALE
移动端,PC端,微信等常用平台和浏览器判断
Office 365 Group概述以及创建方法
基于CC2530 E18-MS1-PCB Zigbee DIY作品(三)
【kali-权限提升】(4.2.7)社会工程学工具包:权限维持创建后门、清除痕迹
C#/VB.NET: Extract text and pictures from PowerPoint document
2022.08.06_每日一题
[免费专栏] Android安全之Android Studion 动态调试APK的两种方法
How to suppress alarm storms?
这年头还不来尝试线稿图视频??