剑指 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) {
相关文章
|
16天前
|
人工智能 机器人 C++
【C++/Python】Windows用Swig实现C++调用Python(史上最简单详细,80岁看了都会操作)
【C++/Python】Windows用Swig实现C++调用Python(史上最简单详细,80岁看了都会操作)
|
1月前
|
Python
Python实现数据结构(如:链表、栈、队列等)。
Python实现数据结构(如:链表、栈、队列等)。
34 0
|
1月前
|
编译器 测试技术 C++
【Python 基础教程 01 全面介绍】 Python编程基础全攻略:一文掌握Python语法精髓,从C/C++ 角度学习Python的差异
【Python 基础教程 01 全面介绍】 Python编程基础全攻略:一文掌握Python语法精髓,从C/C++ 角度学习Python的差异
165 0
|
21天前
|
C++ Python
【C++/Python】C++调用python文件
【C++/Python】C++调用python文件
|
29天前
|
搜索推荐 算法 前端开发
各种排序算法及Python源代码
各种排序算法及Python源代码
23 3
|
2月前
|
存储 Java Go
对比 C++ 和 Python,谈谈指针与引用
对比 C++ 和 Python,谈谈指针与引用
55 1
|
算法 前端开发 小程序
Python | C++、Java、Linux、Go、前端、算法资料分享
Python | C++、Java、Linux、Go、前端、算法资料分享
Python | C++、Java、Linux、Go、前端、算法资料分享
|
13天前
|
安全 Java 数据处理
Python网络编程基础(Socket编程)多线程/多进程服务器编程
【4月更文挑战第11天】在网络编程中,随着客户端数量的增加,服务器的处理能力成为了一个重要的考量因素。为了处理多个客户端的并发请求,我们通常需要采用多线程或多进程的方式。在本章中,我们将探讨多线程/多进程服务器编程的概念,并通过一个多线程服务器的示例来演示其实现。
|
13天前
|
程序员 开发者 Python
Python网络编程基础(Socket编程) 错误处理和异常处理的最佳实践
【4月更文挑战第11天】在网络编程中,错误处理和异常管理不仅是为了程序的健壮性,也是为了提供清晰的用户反馈以及优雅的故障恢复。在前面的章节中,我们讨论了如何使用`try-except`语句来处理网络错误。现在,我们将深入探讨错误处理和异常处理的最佳实践。
|
16天前
|
缓存 监控 Python
解密Python中的装饰器:优雅而强大的编程利器
Python中的装饰器是一种强大而又优雅的编程工具,它能够在不改变原有代码结构的情况下,为函数或类添加新的功能和行为。本文将深入解析Python装饰器的原理、用法和实际应用,帮助读者更好地理解和利用这一技术,提升代码的可维护性和可扩展性。

热门文章

最新文章