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

LCR 155. 将二叉搜索树转化为排序的双向链表

LCR 155. 将二叉搜索树转化为排序的双向链表

LCR 155. 将二叉搜索树转化为排序的双向链表

参考题解

前言

什么是循环双链表?

双向链表又称双链表,是链表的一种数据结构类型,其每个数据结点包含两个指针,分别指向直接前驱和直接后继,支持从前驱或后继任意结点进行双向遍历。通常采用双向循环链表结构实现,该结构通过头尾结点互连形成闭环。

什么是二叉搜索树?

关键性质:左 < 根 < 右

二叉搜索树(BST)又称二叉查找树或二叉排序树。

在二叉搜索树中:

  1. 若任意结点的左子树不空,则左子树上所有结点的值均不大于它的根结点的值。

  2. 若任意结点的右子树不空,则右子树上所有结点的值均不小于它的根结点的值。

  3. 任意结点的左、右子树也分别为二叉搜索树

中序遍历

核心思想:左根右

解法思想

首先,从题目可以知道,最终要是要将二叉搜索树转换为一个已排序的双向循环链表,而在二叉树的遍历中,中序遍历恰好可以将一个二叉搜索树转换为一个有序地数组

因此,本题可以采用中序遍历的思想

函数解析

dfs函数 – 深度优先遍历

如果当前遍历的节点为null,那就说明当前访问的是叶子节点,直接返回。(因为深度优先遍历函数下去完之后肯定是要从二叉树的最下边开始回来的)

递归当前的节点的左节点:dfs(cur.left)

构建双链表:

  • 判断pre节点是否为null,如果是,那就说明当前节点cur是头结点
  • 如果不为null,那就 pre.right = cur,构建pre的后继指针
  • 接着构建cur的前驱指针,cur.left = pre
  • 构建好当前节点之后,接着构建下一个节点,pre就要替代cur的位置
  • 递归当前节点的右结点:dfs(cur.right)
public void dfs(Node cur) {if(cur == null) {return;}dfs(cur.left);if(pre != null) {pre.right = cur;} else {head = cur;} cur.left = pre;pre = cur;dfs(cur.right);
}

treeToDoublyList函数

  • 如果当前节点root为空,直接返回root或者null
  • 转化为双链表:dfs(root)
  • 构建循环双链表:头结点head要指向pre的后继指针,pre指向head的前驱指针
  • 返回head

关于pre

在构建双链表阶段,当cur遍历完最后一个节点的时候,就会继续遍历下一个节点,但下一个节点为null,而pre就会替代原本cur的位置,所以pre就会成为链表的尾结点。

public Node treeToDoublyList(Node root) {if(root == null) return root;dfs(root); // 构建双链表head.left = pre;pre.right = head;return head; 
}

完整代码展示

class Solution {Node pre, head;public Node treeToDoublyList(Node root) {if(root == null) return root;dfs(root); // 构建双链表head.left = pre;pre.right = head;return head; }public void dfs(Node cur) {if(cur == null) {return;}dfs(cur.left);if(pre != null) {pre.right = cur;} else {head = cur;} cur.left = pre;pre = cur;dfs(cur.right);}
}

end…

http://www.hskmm.com/?act=detail&tid=35375

相关文章:

  • 解释这些区块链核⼼概念:区块、交易、Merkle Tree、共识机制(PoW、PoS)、Gas Fee 原理1
  • Claude code cli 的think mode到底是啥?
  • 【VM虚拟机共享主机代理】2025年10月20日可以pass的一些配置
  • 玄机——Linux后门应急
  • 2025/10/20
  • UI弹窗遮罩屏蔽触发事件的处理
  • newDay13
  • 小整数的地址
  • 概率论
  • 一次XFS死锁问题分析
  • P11150 [THUWC 2018] 字胡串
  • 推荐系统与机器学习在会员服务中的应用
  • ManySpeech.MoonshineAsr 使用指南
  • 日志|JAVAWEB|maven
  • QT_基础
  • 2022 ICPC Hangzhou G and 2022 ICPC Jinan
  • C++在类定义内的函数包含static代表什么含义呢?
  • 2025/10/20~2025/?/? 做题笔记 - sb
  • 10-20 Extra-Problem 总结
  • ansible底层文件传输机制中默认模式遇到权限拒绝后启用管道模式可以得到解决
  • 10月20日记
  • Rust 编译加速的最佳实践
  • 20232304 2025-2026-1 《网络与系统攻防技术》实验三实验报告
  • 笔记本 光驱 的内部结构及用法: 应急强大的系统启动 (恢复) 光盘 (DVD+R/RW)
  • Android 源码解析系列1- Android init 进程启动流程
  • 分层图
  • 10.20总结
  • 学习相关
  • 题解:Luogu P10644 [NordicOI 2022] 能源网格 Power Grid
  • 题解:Luogu P10004 [集训队互测 2023] Permutation Counting 2