LCR 155. 将二叉搜索树转化为排序的双向链表（二叉搜索树中序遍历）-程序员宅基地

技术标签：算法 c++ 链表 leetcode LCR(剑指offer) 数据结构

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

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

示例 1：

输入：root = [4,2,5,1,3] 
输出：[1,2,3,4,5]

解释：下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。

示例 2：

输入：root = [2,1,3]
输出：[1,2,3]

示例 3：

输入：root = []
输出：[]
解释：输入是空树，所以输出也是空链表。

示例 4：

输入：root = [1]
输出：[1]

提示：

-1000 <= Node.val <= 1000
Node.left.val < Node.val < Node.right.val
Node.val 的所有值都是独一无二的
0 <= Number of Nodes <= 2000

思路：

1、二叉排序树的中序遍历结果即为有序列表。

2、分别定义一个空的前驱结点pre和一个空的需要返回的头结点head。

3、中序遍历至最左结点处，利用刚开始head为空的条件让head等于最小结点。

4、只有刚开始前驱结点pre为空，后面的遍历pre都不为空。除了刚开始，我们让pre右子树（后继）等于root，root的左子树（前驱）等于pre，即完成有序双向链表的建立。

5、pre=root，继续完成中序遍历，该遍历当前结点的右子树了。

6、最后pre指向最大结点处，我们让pre后继指向head，head前驱指向pre，返回head，完成！

代码实现：

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root == NULL)
            return NULL;
        mid(root);                      //二叉搜索树中序遍历
        head->left = pre;
        pre->right = head;
        return head;
    }
    void mid(Node* root)
    {
        if(root == NULL)                //递归结束条件
            return;
        mid(root->left);
        if(!head)                       //只有在head为空，此时遍历到最小结点处，我们让head等于最小结点
            head = root;
        if(pre)                         //刚开始pre为空，我们需要此条件来跳过第一次的后继链表构建
            pre->right = root;
        root->left = pre;
        pre = root;
        mid(root->right);
    }
private:
    Node* head = NULL;
    Node* pre = NULL;
};

本文链接：https://blog.csdn.net/m0_72855061/article/details/136417129

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

设计模式-原型模式（Prototype）-程序员宅基地

文章浏览阅读67次。原型模式是一种对象创建型模式，它采用复制原型对象的方法来创建对象的实例。它创建的实例，具有与原型一样的数据结构和值分为深度克隆和浅度克隆。浅度克隆：克隆对象的值类型（基本数据类型），克隆引用类型的地址；深度克隆：克隆对象的值类型，引用类型的对象也复制一份副本。UML图：具体代码：浅度复制：import java.util.List;/*..._prototype 设计模式

文章浏览阅读59次。入选国内首批云计算服务创新发展试点城市的北京、上海、深圳、杭州和无锡起到了很好的示范作用，不仅促进了当地产业的升级换代，而且为国内其他城市发展云计算产业提供了很好的借鉴。据了解，目前国内至少有20个城市确定将云计算作为重点发展的产业。这势必会形成新一轮的云计算基础设施建设的**。由于云计算基础设施建设具有投资规模大，运维成本高，投资回收周期长，地域辐射性强等诸多特点，各地在建...

STM32问题集之BOOT0和BOOT1的作用_stm32boot0和boot1作用-程序员宅基地

文章浏览阅读9.4k次，点赞2次，收藏20次。一、功能及目的在每个STM32的芯片上都有两个管脚BOOT0和BOOT1，这两个管脚在芯片复位时的电平状态决定了芯片复位后从哪个区域开始执行程序。BOOT1=x BOOT0=0 // 从用户闪存启动，这是正常的工作模式。BOOT1=0 BOOT0=1 // 从系统存储器启动，这种模式启动的程序_stm32boot0和boot1作用

C语言函数递归调用-程序员宅基地

文章浏览阅读3.4k次，点赞2次，收藏22次。C语言函数递归调用_c语言函数递归调用

明日方舟抽卡模拟器wiki_明日方舟bilibili服-明日方舟bilibili服下载-程序员宅基地

文章浏览阅读410次。明日方舟bilibili服是一款天灾驾到战斗热血的创新二次元废土风塔防手游，精妙的二次元纸片人设计，为宅友们源源不断更新超多的纸片人老婆老公们，玩家将扮演废土正义一方“罗德岛”中的指挥官，与你身边的感染者们并肩作战。与同类塔防手游与众不同的几点，首先你可以在这抽卡轻松获得稀有，同时也可以在战斗体系和敌军走位机制看到不同。明日方舟bilibili服设定：1、起因不明并四处肆虐的天灾，席卷过的土地上出..._明日方舟抽卡模拟器

随便推点

Maven上传Jar到私服报错：ReasonPhrase: Repository version policy: SNAPSHOT does not allow version: xxx_repository version policy snapshot does not all-程序员宅基地

文章浏览阅读437次。Maven上传Jar到私服报错：ReasonPhrase: Repository version policy: SNAPSHOT does not allow version: xxx_repository version policy snapshot does not all

斐波那契数列、素数、质数和猴子吃桃问题_斐波那契日-程序员宅基地

文章浏览阅读1.2k次。斐波那契数列（Fibonacci Sequence）是由如下形式的一系列数字组成的：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …上述数字序列中反映出来的规律，就是下一个数字是该数字前面两个紧邻数字的和，具体如下所示：示例：比如上述斐波那契数列中的最后两个数，可以推导出34后面的数为21+34=55下面是一个更长一些的斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,_斐波那契日

PHP必会面试题_//该层循环用来控制每轮冒出一个数需要比较的次数-程序员宅基地

文章浏览阅读363次。PHP必会面试题1. 基础篇1. 用 PHP 打印出前一天的时间格式是 2017-12-28 22:21:21？ //>>1.当前时间减去一天的时间，然后再格式化echo date('Y-m-d H:i:s',time()-3600*24);//>>2.使用strtotime，可以将任何字符串时间转换成时间戳，仅针对英文echo date('Y-m-d H:i:s',str..._//该层循环用来控制每轮冒出一个数需要比较的次数

windows用mingw(g++)编译opencv，opencv_contrib，并install安装_opencv mingw contrib-程序员宅基地

文章浏览阅读1.3k次，点赞26次，收藏26次。windows下用mingw编译opencv貌似不支持cuda，选cuda会报错，我无法解决，所以没选cuda，下面两种编译方式支持。打开cmake gui程序，在下面两个框中分别输入opencv的源文件和编译目录，build-mingw为你创建的目录，可自定义命名。1、如果已经安装Qt，则Qt自带mingw编译器，从Qt安装目录找到编译器所在目录即可。1、如果已经安装Qt，则Qt自带cmake，从Qt安装目录找到cmake所在目录即可。2、若未安装Qt，则安装Mingw即可，参考我的另外一篇文章。_opencv mingw contrib

5个高质量简历模板网站，免费、免费、免费_hoso模板官网-程序员宅基地

文章浏览阅读10w+次，点赞42次，收藏309次。今天给大家推荐5个好用且免费的简历模板网站，简洁美观，非常值得收藏！1、菜鸟图库https://www.sucai999.com/search/word/0_242_0.html?v=NTYxMjky网站主要以设计类素材为主，办公类素材也很多，简历模板大部个偏简约风，各种版式都有，而且经常会更新。最重要的是全部都能免费下载。2、个人简历网https://www.gerenjianli.com/moban/这是一个专门提供简历模板的网站，里面有超多模板个类，找起来非常方便，风格也很多样，无须注册就能免费下载，_hoso模板官网

通过 TikTok 联盟提高销售额的 6 个步骤_tiktok联盟-程序员宅基地

文章浏览阅读142次。你听说过吗？该计划可让您以推广您的产品并在成功销售时支付佣金。它提供了新的营销渠道，使您的产品呈现在更广泛的受众面前并提高品牌知名度。此外，TikTok Shop联盟可以是一种经济高效的产品或服务营销方式。您只需在有人购买时付费，因此不存在在无效广告上浪费金钱的风险。这些诱人的好处是否足以让您想要开始您的TikTok Shop联盟活动？如果是这样，本指南适合您。_tiktok联盟