剑指 Offer 36. 二叉搜索树与双向链表--------python && C++源代码

简介: 剑指 Offer 36. 二叉搜索树与双向链表--------python && C++源代码

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


难度中等504收藏分享切换为英文接收动态反馈


输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。


为了让您更好地理解问题,以下面的二叉搜索树为例:


image.png


我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。


下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。


image.png


特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。


题目思路:

力扣


借用一下K神的图 一看图解决一切问题 ,本来想自己写题解,后来发现人家的图画的太好了 直接转载一下:


image.png


Python代码:

class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: return
            dfs(cur.left)
            if self.pre: self.pre.right , cur.left = cur , self.pre
            else: self.head = cur
            self.pre = cur
            dfs(cur.right)
        if not root: return 
        self.pre = None
        dfs(root)
        self.head.left , self.pre.right = self.pre , self.head
        return self.head

C++代码:

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (root==nullptr) return nullptr;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
private:
    Node *head , *pre;
    void dfs(Node *cur){
        if(cur==nullptr) return ;
        dfs(cur->left);
        if(pre!=nullptr) {
相关文章
|
8月前
|
存储 人工智能 运维
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
464 48
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
|
7月前
|
机器学习/深度学习 存储 算法
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
|
8月前
|
人工智能 Python
【02】做一个精美的打飞机小游戏,python开发小游戏-鹰击长空—优雅草央千澈-持续更新-分享源代码和游戏包供游玩-记录完整开发过程-用做好的素材来完善鹰击长空1.0.1版本
【02】做一个精美的打飞机小游戏,python开发小游戏-鹰击长空—优雅草央千澈-持续更新-分享源代码和游戏包供游玩-记录完整开发过程-用做好的素材来完善鹰击长空1.0.1版本
242 7
|
3月前
|
Java C++
c++ 红黑树(自平衡二叉搜索树)(k,v型)
因为红黑树是一种特殊的AVL树(但少了平衡因子的存在),所以其结点的定义是在AVL树上加上新的成员变量,用于表示结点的颜色。RED,BLACK,//三叉链, _kv(kv){}首先我们在默认构造上,默认构造结点的颜色默认情况下为红色所以为什么构造结点时,默认将结点的颜色设置为红色?这是因为:当我们向红黑树插入结点时,若我们插入的是黑色结点,那么插入路径上黑色结点的数目就比其他路径上黑色结点的数目多了一个,即破坏了红黑树的性质4,此时我们就需要对红黑树进行调整。
93 0
|
8月前
|
测试技术 Python
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
343 31
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
|
12月前
|
移动开发 Python Windows
python编程获取网页标题title的几种方法及效果对比(源代码)
python编程获取网页标题title的几种方法及效果对比(源代码)
|
7月前
|
C++ 容器
c++中的二叉搜索树
c++中的二叉搜索树
|
8月前
|
存储 算法 安全
U 盘管控情境下 Python 二叉搜索树算法的深度剖析与探究
在信息技术高度发达的今天,数据安全至关重要。U盘作为常用的数据存储与传输工具,其管控尤为关键。本文探讨Python中的二叉搜索树算法在U盘管控中的应用,通过高效管理授权U盘信息,防止数据泄露,保障信息安全。二叉搜索树具有快速插入和查找的优势,适用于大量授权U盘的管理。尽管存在一些局限性,如树结构退化问题,但通过优化和改进,如采用自平衡树,可以有效提升U盘管控系统的性能和安全性。
94 3
|
10月前
|
测试技术 开发者 Python
使用Python解析和分析源代码
本文介绍了如何使用Python的`ast`模块解析和分析Python源代码,包括安装准备、解析源代码、分析抽象语法树(AST)等步骤,展示了通过自定义`NodeVisitor`类遍历AST并提取信息的方法,为代码质量提升和自动化工具开发提供基础。
720 9
|
11月前
|
安全 Linux 数据安全/隐私保护
python知识点100篇系列(15)-加密python源代码为pyd文件
【10月更文挑战第5天】为了保护Python源码不被查看,可将其编译成二进制文件(Windows下为.pyd,Linux下为.so)。以Python3.8为例,通过Cython工具,先写好Python代码并加入`# cython: language_level=3`指令,安装easycython库后,使用`easycython *.py`命令编译源文件,最终生成.pyd文件供直接导入使用。
346 3
python知识点100篇系列(15)-加密python源代码为pyd文件

推荐镜像

更多