当前位置: 首页 > news >正文

可视化图解算法: 二叉搜索树转双向排序链表

1. 题目

描述

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

数据范围:输入二叉树的节点数 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
树的形状如上图       

2. 解题思路


二叉树转双向链表可以通过两步来完成:首先确定双向链表的头结点(头节点:二叉树最左侧的节点);之后再通过递归将二叉树转为双向链表。二叉树转双向链表可以通过两步来完成:首先确定双向链表的头结点(头节点:二叉树最左侧的节点);之后再通过递归将二叉树转为双向链表。

具体操作步骤如下:

假如需要转换的二叉搜索树结构如下图所示:

步骤一:首先确定双向链表的头结点。

二叉搜索树具有以下特点:

  • 每个节点最多有两个子节点:左子节点右子节点

  • 节点的值关系

    • 左子树中所有节点的值 小于 当前节点的值。

    • 右子树中所有节点的值 大于 当前节点的值。

中序遍历结果是有序序列:对二叉搜索树进行中序遍历(左 → 根 → 右),可以得到一个升序排列的数值序列。

根据题目的要求,需要将二叉搜索树转换为有序链表。而对于二叉搜索树来说最左侧的节点值是最小的,因此可以将二叉搜索树最左侧的节点作为双向链表的头结点。

步骤二:通过递归将二叉树转为双向链表。

如果将二叉搜索树通过中序遍历(左 → 根 → 右),可以得到一个升序排列的结果。因此可以通过二叉搜索树中序遍历的思想来实现链表的转换。

对于递归来说,我们写递推公式时只需考虑两层的关系(即:f(n)与f(n-1)之间的关系,递归详细内容讲解可以参考《递归》一篇的文章),这时我们可以将二叉树进行简化:

定义变量pre,初始化时为Null。pre变量指向如下图所示:

对于这样一颗二叉树来说,可以通过3步将其转换为双向链表:

①更改root的左指针,让它指向左子树,root.left=pre。

②更改左子树的右指针,让它指向root,pre.right=root。

③移动操作节点变量,让它指向root(便于进行下一轮的递归),pre=root。

对应的递推公式如下:

有了递推公式,就可以很方便的写出代码。

如果文字描述的不太清楚,你可以参考视频的详细讲解。

  • Python版本:https://www.bilibili.com/cheese/play/ep1371846https://www.bilibili.com/cheese/play/ep1371846

  • Java版本:数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367111

  • Golang版本:https://www.bilibili.com/cheese/play/ep1364651https://www.bilibili.com/cheese/play/ep1364651

3. 编码实现

核心代码如下:

/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* @param pRootOfTree TreeNode类
* @return TreeNode类*/
func Convert(pRootOfTree *TreeNode) *TreeNode {// write code hereif pRootOfTree == nil {return nil}//1.查找二叉搜索树最左侧的节点p := pRootOfTreefor p.Left != nil {p = p.Left //找到链表的头(最左侧的二叉树节点)}//2.通过中序遍历的方法转换二叉树为链表inOrder(pRootOfTree)return p}var pre *TreeNode //定义一个前序节点func inOrder(root *TreeNode) {// 2. 递归终止条件if root == nil {return}// 1. 问题分解(递推公式)// 1.1 到左子树进行相似的处理inOrder(root.Left)// 1.2 对当前节点进行处理root.Left = pre //当前节点的左指针指向前序节点if pre != nil {pre.Right = root //前序节点的右指针指向当前节点}pre = root //移动指针变量// 1.3 到右子树进行相似的处理inOrder(root.Right)}

具体完整代码你可以参考下面视频的详细讲解。

  • Python版本:https://www.bilibili.com/cheese/play/ep1371846https://www.bilibili.com/cheese/play/ep1371846

  • Java版本:https://www.bilibili.com/cheese/play/ep1367111https://www.bilibili.com/cheese/play/ep1367111

  • Golang版本:数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364651

4.小结

二叉树转双向链表可以通过两步来完成:首先确定双向链表的头结点(头节点:二叉树最左侧的节点);之后再通过递归中序遍历的思想将二叉树转为双向链表。


《数据结构与算法》深度精讲课程正式上线啦!七大核心算法模块全解析:

✅ 链表 ✅ 二叉树 ✅二分查找、排序 ✅ 堆、栈、队列 ✅回溯算法 ✅ 哈希算法 ✅ 动态规划

无论你是备战笔试面试、提升代码效率,还是突破技术瓶颈,这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡,与千名开发者共同进阶!

  • Python编码实现:哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss897667807

  • Java编码实现:https://www.bilibili.com/cheese/play/ss161443488https://www.bilibili.com/cheese/play/ss161443488

  • Golang编码实现:https://www.bilibili.com/cheese/play/ss63997https://www.bilibili.com/cheese/play/ss63997

对于二叉树的相关算法,我们总结了一套【可视化+图解】方法,依据此方法来解决相关问题,算法变得易于理解,写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句:人皆知有用之用,而莫知无用之用也。

http://www.xdnf.cn/news/182791.html

相关文章:

  • Spdlog 日志组件的安装及使用
  • 【C语言】程序分配的区域
  • spring框架学习(下)
  • 现场问题排查-postgresql某表索引损坏导致指定数据无法更新影响卷宗材料上传
  • Java异常处理全面指南:从基础到高级实践
  • (done) 吴恩达版提示词工程 6. 转换 (翻译,通用翻译,语气风格变换,文本格式转换,拼写检查和语法检查)
  • 关于定时任务原理
  • Python实例题:Python气象数据分析
  • 猿人学web端爬虫攻防大赛赛题第15题——备周则意怠-常见则不疑
  • Linux Centos8使用yum命令安装mysql8
  • 《100天精通Python——基础篇 2025 第9天:字典操作全解析与哈希原理揭秘》
  • SAE 实现应用发布全过程可观测
  • 将你的本地项目发布到 GitHub (新手指南)
  • 00-算法打卡-目录
  • Using the NCCL Library: A Practical Guide
  • Ubuntu安装SSH服务
  • android Observable 和Observer 是什么
  • 全金属机柜散热风扇:高效散热的核心装备
  • 英文中日期读法
  • Spring Boot 中多线程的基础使用
  • madvise MADV_FREE对文件页统计的影响及原理
  • SALOME源码分析:Geomtry模块
  • Flutter Dart中的抽象类 多态 和接口
  • Go语言之路————指针、结构体、方法
  • 【EEGLAB】使用pop_loadset读取.set文件,报错找不到对应的.fdt文件。
  • 《Learning Langchain》阅读笔记10-RAG(6)索引优化:MultiVectorRetriever方法
  • Java 设计模式心法之第30篇 - 返璞归真:设计模式与 SOLID 原则的深度融合
  • Git和Gitlab的部署和操作
  • OurBMC技术委员会2025年一季度例会顺利召开
  • 微博安卓版话题热度推荐算法与内容真实性分析