面试经典(24)--二叉搜索树和双向链表

2023-11-09

题目描述:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。


算法分析:使用后续遍历方法。从10节点开始分析,只要左子树返回最大节点,右子树返回最小节点即可。正常递归无法判定当前是左子树还是右子树,所以参数要假如bool值判定左右子树。

//将二叉树搜索树改成双向链表
struct Node *convertNode(struct Node *pNode,bool asRight)
{
	if(!pNode)
		return NULL;
	struct Node *pLeft;
	struct Node *pRight;

	//递归修改左子树
	pLeft=convertNode(pNode->left,false);

	//当前节点和左子树链连接
	if(pLeft)
		pLeft->right=pNode;
	pNode->left=pLeft;


	//递归修改右子树
	pRight=convertNode(pNode->right,true);

	//当前节点和右子树连接,注意判定条件不要忘记
	if(pRight)
		 pRight->left=pNode;
	pNode->right=pRight;


	struct Node* pTemp=pNode;

	//根据asRight返回最大或者最小节点
	if(asRight)
		while(pTemp->left)
			pTemp=pTemp->left;
	else
		while(pTemp->right)
			pTemp=pTemp->right;
	return pTemp;
}


本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

面试经典(24)--二叉搜索树和双向链表 的相关文章

  • qt 实现翻金币游戏

    游戏玩法介绍 游戏设置关卡二十关 通过选关界面可以选择进入到对应的关卡中 进入对应关卡之后 点击任意金币 可以使该硬币以及周边 上 下 左 右 金边翻转 如果硬币都翻转为金币 则游戏胜利 游戏界面设置 开始界面 开始场景中需要自定义一个按钮
  • MyBatis实现简单的增删查改操作(XML配置)

    最近在跟着B站传智的课程学习SSM 先学的是MyBatis 写一篇博客记录一下如何利用MyBatis实现简单的增删查改 主要是记录一下实现过程 实现思路 注意事项 避坑 本教程使用XML配置进行实现 一 软件环境 Java IDEA mys
  • Windows下,Hexo+GitHub搭建博客

    一 注册GitHub账号 二 创建GitHub仓库 创建git仓库时候 仓库的名称有格式要求 例如我的GitHub仓库用户名是thinkerwalker 那么我创建的仓库名称就是thinkerwalker github io 此处的警告是因
  • 2D人体姿态估计 - Convolutional Pose Machines(CPM)

    https github com namedBen Convolutional Pose Machines Pytorch https github com timctho convolutional pose machines tenso
  • QFileDialog打开文件夹,获得文件名(getOpenFileName,getExistingDirectory)

    1 QFileDialog getOpenFileName 示例 括号里的参数分别是 指定父类窗口部件 对话框使用的标题 默认打开后显示的目录 即告诉它从哪一级目录开始 右下角的文件过滤器 QString file name QFileDi
  • MongoDB复制集数据是如何复制的

    MongoDB 复制集 MongoDB复制集的主要意义在于实现服务高可用 类似于Redis中的哨兵模式 它主要提供两个方面的功能 1 数据写入主节点 Primary 时将数据复制到另一个副本节 Secondary 点上 2 主节点发生故障时

随机推荐

  • Android UI 之居中绘制文本内容的正确方法——实现自定义一个TextView

    原文地址 http blog csdn net carrey1989 article details 10399727 我们在自定义一个控件的时候 有时候会需要自己来绘制一些文本内容 这样就自然而然遇到确定文本的方位的问题 比如文本需要水平
  • 蓝桥杯-最少砝码(2021题)

    问题描述 你有一架天平 现在你要设计一套砝码 使得利用这些砝码可以称出任意 小于等于 NN 的正整数重量 那么这套砝码最少需要包含多少个砝码 注意砝码可以放在天平两边 输入格式 输入包含一个正整数 N 输出格式 输出一个整数代表答案 样例输
  • Java实现Excel导入导出操作详解

    前言 本次封装是基于 POI 的二次开发 最终使用只需要调用一个工具类中的方法 就能满足业务中绝大部门的导入和导出需求 1 功能测试 1 1 测试准备 在做测试前 我们需要將 2 环境准备 中的四个文件拷贝在工程里 如 我这里均放在了com
  • AD20笔记-PCB设计

    AD20笔记 文章目录 AD20笔记 PCB设计 新建PCB 导入原理图元器件 估计板子的大小 隐藏网络 机械层绘制放置区域 设置原点 设置板子大小 层叠管理器 正片负片 模块化分布 导入DXF文件 单独查看某一层 相连走线选择 精准移位吸
  • 解析隐式类型转换操作operator double() const,带你了解隐式转换危害有多大

    目录 前言 隐式类型转换操作符 使用注意 解决方案 深思 构造函数造成的隐式转换 分析 总结 解决方案 explicit关键字 引入Proxy classes 代理类 总结 前言 我首次看到这种函数的时候是在Flightgear飞行模拟器的
  • scatter绘制散点图示例

    scatter绘制散点图示例 1 example 1 from sklearn import datasets digits datasets load digits import matplotlib pyplot as plt colo
  • Pytorch学习(6) —— 加载模型部分参数的用法

    上一节 我们给出了模型加载和保存的简要示例 但是 我们有时候会用别人的参数 他们的层参数名和我们的名称很容易不同 因此这里将会对源码进入深入剖析 分析参数提取和保存是如何实现的 我们使用pytorch的VGG16预训练模型 加载 返回其类型
  • 【云原生之kubernetes】helm在k8s集群中的基本使用

    云原生之kubernetes helm在k8s集群中的基本使用 一 检查kubernetes环境 1 检查kubernetes节点状态 2 检查helm状态 二 helm的V2版本和V3版本区别 1 主要区别 2 版本架构的变化 3 V3版
  • STM32写的PID算法温度控制程序示例

    使用STM32写的PID算法温度控制程序示例 该程序通过读取温度传感器的数据 并采用PID控制算法 输出PWM信号来控制加热器的工作 以实现温度的稳定控制 include stm32f10x h define TIM PERIOD Syst
  • C++和QML之间传输JSON字符串并解析(适用于传数组或其他复杂参数)

    QJsonObject转为QString 发送带此QString的信号 QML中接收到信号后直接用JSON进行解析 QML支持Javascript 自然也支持相应的json解析 同理 可以在QML中将javascript对象先转换成json
  • 这几款好用的数据分析软件推荐给你

    随着互联网和大数据时代的到来 数据分析已成为越来越多公司和个人必备的技能之一 而在进行数据分析时 一个好用 功能齐全的数据分析软件是至关重要的工具 在市场上 有很多不同的数据分析软件可供选择 但其中哪些才是最好的呢 今天我将向大家介绍几款我
  • 手撸代码-链表中的节点每k个一组翻转-牛客

    描述 将给出的链表中的节点每 k k 个一组翻转 返回翻转后的链表 如果链表中的节点数不是 k k 的倍数 将最后剩下的节点保持原样 你不能更改节点中的值 只能更改节点本身 要求空间复杂度 O 1 O 1 例如 给定的链表是1 2 3 4
  • JQuery的链式编程与隐式迭代

  • 华为OD机试真题-投篮大赛【2023.Q1】

    题目内容 你现在是一场采用特殊赛制投篮大赛的记录员 这场比赛由若干回合组成 过去几回合的得分可能会影响以后几回合的得分 比赛开始时 记录是空白的 你会得到一个记录操作的字符串列表 ops 其中ops i 是你需要记录的第i项操作 ops遵循
  • pytorch中一维卷积Conv1d简介

    最近在使用pytorch中的一维卷积来对文本进行处理 进行文本分类任务 查阅了网上相关的博客还有api这里做一个总结 一维卷积 顾名思义就是在一维空间上进行卷积 通常用来处理时序的数据 卷积的过程如下图 进行卷积的数据形状为 batch s
  • IntelliJ IDEA 使用教程

    一 设置入口 1 快捷键 Ctrl Alt S 2 File gt Settings 3 View gt appearance gt Toolbar 单击选中 出现工具栏图标 以后可直接点击它进入设置界面 之后的相关设置后 请点击Apply
  • 列车调度问题PTA

    7 20 列车调度 25 分 火车站的列车调度铁轨的结构如下图所示 两端分别是一条入口 Entrance 轨道和一条出口 Exit 轨道 它们之间有N条平行的轨道 每趟列车从入口可以选择任意一条轨道进入 最后从出口离开 在图中有9趟列车 在
  • Python 正则表达式(完整)-------附LeetCode真题详细解析

    正则表达式 又称规则表达式 Regular Expression 在代码中常简写为regex regexp或RE 是一种文本模式 包括普通字符 例如 a 到 z 之间的字母 和特殊字符 称为 元字符 是计算机科学的一个概念 正则表达式使用单
  • pread

    pread is a system call in Linux that allows reading data from a file descriptor at a specified offset without changing t
  • 面试经典(24)--二叉搜索树和双向链表

    题目描述 输入一棵二叉搜索树 将该二叉搜索树转换成一个排序的双向链表 算法分析 使用后续遍历方法 从10节点开始分析 只要左子树返回最大节点 右子树返回最小节点即可 正常递归无法判定当前是左子树还是右子树 所以参数要假如bool值判定左右子