剑指 offer 36. 二叉搜索树与双向链表

news/2024/11/7 20:39:15/

描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示
在这里插入图片描述

数据范围:输入二叉树的节点数 0≤n≤1000,二叉树中每个节点的值 0≤val≤1000,要求:空间复杂度 O(1)(即在原树上操作),时间复杂度 O(n)

注意:
1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构
4.你不用输出双向链表,程序会根据你的返回值自动打印输出
输入描述:
二叉树的根节点
返回值描述:
双向链表的其中一个头节点。

示例1
输入:
{10,6,14,4,8,12,16}
返回值:
From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明:
输入题面图中二叉树,输出的时候将双向链表的头节点返回即可。

示例2
输入:
{5,4,#,3,#,2,#,1}
返回值:
From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明:
5
/
4
/
3
/
2
/
1
树的形状如上图

思路:最常规的思路就是中序遍历,对于BST 数,中序遍历就是一个有序的列表,然后把列表转成一个双向队列就ok,由于题目要求空间复杂度 O(1), 我们可以在中序遍历的时候对原有的树做一些变换,在数的基础上进行调整,这样就不用再申请额外的空间了。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None#
# 
# @param pRootOfTree TreeNode类 
# @return TreeNode类
#
class Solution:def __init__(self):self.prevNode = Nonedef convert2LinkList(self, root):if root == None:returnself.convert2LinkList(root.left)if self.prevNode != None:self.prevNode.right = rootroot.left = self.prevNodeself.prevNode = rootself.convert2LinkList(root.right)def Convert(self , pRootOfTree ):# write code hereif pRootOfTree == None:return Nonehead = pRootOfTreewhile head.left != None:head = head.leftself.convert2LinkList(pRootOfTree)return head

http://www.ppmy.cn/news/706816.html

相关文章

2023夏-杂牌ngff的sata固态使用primocache的性能提升

测试的固态是作为系统盘并且写入三分之二的杂牌sata协议固态,性能偏低但还可以用的程度 用了增强的软件是 PrimoCache4.2 之前的跑分是360,很低了但还能正常使用,4k的读取速度很低 安装并配置内存500m的读写缓存后 聊胜于无吧,多多…

ModaHub魔搭社区:Milvus 数据迁移工具 – MilvusDM

目录 Milvus 数据迁移工具 — MilvusDM 简介 功能介绍 Faiss to Milvus Milvus 数据迁移工具 — MilvusDM 简介 MilvusDM 是一款针对 Milvus 研发的数据迁移工具,支持 Milvus 数据传输以及数据文件的导入与导出: Faiss to Milvus:将未…

MySQL意向锁(Intent Lock)

当我们想要获取某个数据表的排它锁的时候,需要先看下这张数据表有没有上了排它锁。如果这个数据表中的某个数据行被上了行锁,我们就无法获取排它锁。这时需要对数据表中的行逐一排查,检查是否有行锁,如果没有,才可以获…

华为mate40营销之我见

华为mate40营销之我见 产品策略 华为深厚的创新研发实力也为华为手机产品提供了保障,不仅拥有多项专利,还成功自主研发芯片,2016全球企业研发投入排行榜中华为排名世界第八、中国第一。华为智能手机主要采取差异化策略,针对不同…

华为P40博客营销

华为创立于1987年,是全球领先的ICT(信息与通信)基础设施和智能终端提供商,我们致力于把数字世界带入每个人、每个家庭、每个组织,构建万物互联的智能世界:让无处不在的联接,成为人人平等的权利&…

华为发布会: 牛逼鸿蒙,吹水的大会

前天,华为举行了一场盛大的发布会,会议开头介绍了华为在消费者市场所取得的成绩,说实话,看了还挺震撼的,华为确实是一家很厉害的商业公司。 后面就开始介绍鸿蒙 OS 了。 我研究过几年的 Linux 内核,对操作…

华为P9遭疯抢,首发3分钟售罄;苹果汽车概念图遭权威杂志曝光引热议;中科大机器人太逼真

不可不知 1 京东到家与众包物流平台达达合并 新公司保持独立运营 京东旗下O2O子公司京东到家昨日宣布并购众包物流平台“达达”。并购完成后,京东将以京东到家的资产、京东集团的业务资源以及两亿美元现金换取新达达约47.4%的股份并成为单一最大股东。合并后的新公…

华为手表广告营销案例和广告策划案例PPT模板

模板介绍 华为手表广告营销案例和广告策划案例PPT模板。一套营销策划幻灯片模板,内含黑色,橙色,蓝色多种配色,风格设计,动态播放效果,精美实用。 希望下面这份精美的PPT模板能给你带来帮助,温馨提示:本资…