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

【5.10】指针算法-快慢指针将有序链表转二叉搜索树

一、题目

        给定一个单链表,其中的 元素按升序排序 ,将其转换为 高度平衡的二叉搜索树
        本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

示例:
给定的有序链表: [ -10 , -3 , 0 , 5 , 9 ],
一个可能的答案是: [ 0 , -3 , 9 , -10 , null , 5 ],
它可以表示下面这个高度平衡二叉搜索树:
          0
        /    \
     -3      9
     /       /

  -10     5

二、解题思路

        二叉搜索树具有这样的特点:当前节点大于左子树的所有节点,同时小于右子树的所有节点,并且每个节点都具备这个特性。

        题中提到,是按照升序排列的单链表,我们只需找到链表的中间节点,使其成为树的根节点。中间节点前面的部分就是根节点左子树的所有节点,中间节点后面的部分就是根节点右子树的所有节点。然后,使用递归的方式再分别对左右子树进行相同的操作……

        这里以链表 1→2→3→4→5 为例来画个图看一下。

        上面链表的中间节点3就是二叉搜索树的根节点,然后再对左右子节点以同样的方式进行操作。最后我们来看看实现代码。

三、代码实现

#include <iostream>
#include <vector>
#include <queue>// 定义链表节点
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 定义树节点
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 将有序链表转换为二叉搜索树
TreeNode* sortedListToBST(ListNode* head) {// 边界条件的判断if (head == nullptr)return nullptr;if (head->next == nullptr)return new TreeNode(head->val);// 通过快慢指针找到链表的中间结点slow,pre就是中间结点slow的前一个结点ListNode* slow = head;ListNode* fast = head;ListNode* pre = nullptr;while (fast != nullptr && fast->next != nullptr) {pre = slow;slow = slow->next;fast = fast->next->next;}// 链表断开为两部分,一部分是node的左子节点,一部分是node的右子节点pre->next = nullptr;// node就是当前节点TreeNode* node = new TreeNode(slow->val);// 从head节点到pre节点是node左子树的节点node->left = sortedListToBST(head);// 从slow.next到链表的末尾是node的右子树的结点node->right = sortedListToBST(slow->next);return node;
}// 打印树的层序遍历结果
void printTreeLevelOrder(TreeNode* root) {if (root == nullptr)return;std::queue<TreeNode*> q;q.push(root);bool first = true;while (!q.empty()) {int size = q.size();for (int i = 0; i < size; ++i) {TreeNode* node = q.front();q.pop();if (!first) {std::cout << ", ";}first = false;if (node != nullptr) {std::cout << node->val;q.push(node->left);q.push(node->right);} else {std::cout << "null";}}}std::cout << std::endl;
}// 创建链表
ListNode* createLinkedList(const std::vector<int>& values) {ListNode* dummy = new ListNode(0);ListNode* current = dummy;for (int val : values) {current->next = new ListNode(val);current = current->next;}return dummy->next;
}int main() {// 输入给定的有序链表:[-10, -3, 0, 5, 9]std::vector<int> values = {-10, -3, 0, 5, 9};ListNode* head = createLinkedList(values);// 将有序链表转换为二叉搜索树TreeNode* root = sortedListToBST(head);// 打印树的层序遍历结果std::cout << "[";printTreeLevelOrder(root);std::cout << "]" << std::endl;return 0;
}

相关文章:

【5.10】指针算法-快慢指针将有序链表转二叉搜索树

一、题目 给定一个单链表&#xff0c;其中的 元素按升序排序 &#xff0c;将其转换为 高度平衡的二叉搜索树 。 本题中&#xff0c;一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表&#xff1a; [ -10 , -3 , 0 , …...

机器学习—前向传播的一般实现

可以写一个函数来实现一个密集的层&#xff0c;那是神经网络的单层&#xff0c;所以定义稠密函数&#xff0c;它将上一层的激活作为输入以及给定层神经元的参数w和b。看下边图片所展示的例子&#xff0c;把所有这些权重向量堆叠成一个矩阵&#xff0c;wnp.array([[1,-3,5][2,4,…...

极狐GitLab 签约足下科技,加速国产智驾操作系统的发展与普及

客户背景 足下科技是一家致力于成为智能汽车软件平台、产品与服务领导者的高科技企业&#xff0c;成立于 2022年 3 月&#xff0c;总部位于深圳市。足下科技自主研发的智能驾驶操作系统 Earth 和 Air 工具链&#xff0c;协助OEM和Tier1厂商降低算法和软件开发难度&#xff0c;…...

20241102在荣品PRO-RK3566开发板的预置Android13下适配宸芯的数传模块CX6603N

20241102在荣品PRO-RK3566开发板的预置Android13下适配宸芯的数传模块CX6603N 2024/11/2 18:04 在WIN10使用程序&#xff1a;ViewLink-4.0.7_0708-windows-x64.exe 在荣品PRO-RK3566开发板的预置Android13下使用&#xff1a;ViewLink-2023_12_21-release-0.2.6.apk adb install…...

力扣(leetcode)题目总结——哈希表篇

leetcode 经典题分类 链表数组字符串哈希表二分法双指针滑动窗口递归/回溯动态规划二叉树辅助栈 本系列专栏&#xff1a;点击进入 leetcode题目分类 关注走一波 前言&#xff1a;本系列文章初衷是为了按类别整理出力扣&#xff08;leetcode&#xff09;最经典题目&#xff0c…...

AWS RDS Oracle hit ORA-39405

报错信息&#xff1a; ORA-39405: Oracle Data Pump does not support importing from a source database with TSTZ version 42 into a target database with TSTZ version 35. 分析过程&#xff1a; 这个报错是由于timezone_file的版本&#xff0c;源端比目标端高&#xf…...

Dinky中配置Flink集群

需要启动yarn-session 进程&#xff0c;在集群服务器 cd /pwd//flink/bin yarn-session -d 启动成功后可以在yarn的资源管理队列进行查看 启动成功后会给出&#xff1a;JobManager Web Interface 在dinky中进行配置&#xff1a; 集群配置 Hadoop 配置&#xff1a; H…...

通讯录(C 语言)

目录 一、通讯录设计思路1. 伪代码设计思路2. 代码设计思路 二、代码实现三、程序运行演示四、整体分析 一、通讯录设计思路 1. 伪代码设计思路 通讯录可以用来存储 100 个人的信息&#xff0c;每个人的信息包括&#xff1a;姓名、性别、年龄、电话、住址。 提供方法&#x…...

对比Java和TypeScript中的服务注册和查找机制

文章目录 一、Java中的服务注册和查找二、TypeScript中的服务注册和查找2.1 使用依赖注入&#xff08;DI&#xff09;框架2.2 injectable原理2.3 使用TypeScript的反射系统实现依赖注入 三、优缺点分析3.1 Java的ServiceLoader3.2 TypeScript的服务注册和查找 四、结论 在构建大…...

Flutter 主流常用第三方库、插件收集

一、Flutter 学习资料 FlutterFlutter官网Flutter中文网咸鱼技术掘金Flutter专栏 Flutter - Dart中(.)、(..)、(...)语法使用_flutter ...-CSDN博客 Flutter pubspec.yaml 配置文件_flutter yaml配置git-CSDN博客 Flutter 添加 example流程_建flutter 工程 怎么自动有example-C…...

【在Linux世界中追寻伟大的One Piece】多路转接select

目录 1 -> I/O多路转接之select 1.1 -> 初识select 1.2 -> select函数原型 1.3 -> 关于fd_set结构 1.4 -> 关于timeval结构 2 -> 理解select执行过程 2.1 -> Socket就绪条件 2.2 -> select特点 2.3 -> select缺点 3 -> select使用示例…...

补一下 二维 平面直角坐标系 到三维

上一篇帖子写到 二维的平面直角坐标系&#xff0c;是那样的&#xff0c;这次补充一下三维的。首先需要&#xff0c;安装一个包&#xff0c;如下&#xff1a; 然后&#xff0c;把参数输入&#xff0c;输入这个坐标系的参数&#xff0c;如下&#xff1a; 这样就可以输出如下的三…...

如何学习Python编程?

如何学习Python编程&#xff1f; 了解基础概念&#xff1a; 学习Python的基本语法&#xff0c;包括变量、数据类型、运算符等。了解控制结构&#xff0c;如条件语句&#xff08;if语句&#xff09;和循环&#xff08;for和while循环&#xff09;。 选择学习资源&#xff1a; 在…...

使用EasyExcel实现导出excel文件时生成多级下拉选

前言 公司有个需求本来只涉及到两个下拉选项&#xff0c;后面就想能不能实现多个下拉选&#xff0c;当然我这里说的多个下拉选是联动的&#xff0c;比如省、地市、区县这种。 实现步骤 1、添加EasyExcel的Maven依赖 <dependency><groupId>com.alibaba</group…...

微信小程序 高校教材征订系统

文章目录 项目介绍具体实现截图技术介绍mvc设计模式小程序框架以及目录结构介绍错误处理和异常处理java类核心代码部分展示详细视频演示源码获取 项目介绍 系统分为三个角色&#xff0c;分别是教材科、系教学秘书、教研室主任。系统主要完成功能是教材科要发布教材征订信息&am…...

从0开始的STM32 定时器(I):聊一聊基本定时器

目录 时钟源 控制器 时基单元 关于HAL库如何配置基本定时器 HAL是如何初始化我们的定时器句柄的 HAL_TIM_Base_Init 开始定时 如何处理句柄&#xff1f; 在我们使用STM32解决一些问题的时候&#xff0c;常常会遇到说&#xff1a;我想要以一个周期做一些事情&#xff1a;…...

vue常见题型(1-10)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 2.2双向绑定的原理是什么vue框架采用的是数据双向绑定的方式&#xff0c;由三个重要部分构成2.2.1.ViewModel2.2.2 双向绑定2.2.3.1.编译Compile2.2.3.2.依赖收集 3…...

【SpringBoot】使用注解进行XSS防御

在Spring Boot中&#xff0c;我们可以使用注解的方式来进行XSS防御。注解是一种轻量级的防御手段&#xff0c;它可以在方法或字段级别对输入进行校验&#xff0c;从而防止XSS攻击。 引入相关依赖 maven依赖&#xff1a; <!--JSR-303/JSR-380用于验证的注解 --> <de…...

华为海思招聘-芯片与器件设计工程师-模拟芯片方向- 机试题-真题套题题目——共8套(每套四十题)

华为海思招聘-芯片与器件设计工程师-模拟芯片方向- 机试题-真题套题题目分享——共九套&#xff08;每套四十题&#xff09; 岗位——芯片与器件设计工程师 岗位意向——模拟芯片 真题题目分享&#xff0c;完整题目&#xff0c;无答案&#xff08;共8套&#xff09; 实习岗位…...

vscode 下载慢的解决方法

下载链接示例&#xff1a;https://az764295.vo.msecnd.net/stable/ccbaa2d27e38e5afa3e5c21c1c7bef4657064247/code1.62.3-1637137107amd64.deb 解决方法&#xff1a; 把 az764295.vo.msecnd.net 替换成 vscode.cdn.azure.cn...

CIC-IDS-2018数据集 代码预处理

CIC-IDS-2018数据集 预处理 数据集的获取地址在 https://aistudio.baidu.com/datasetdetail/60692 第一次登陆&#xff0c;注册就行&#xff0c;内容随便填就能注册 create_sample_data() 在代码中被注释&#xff0c;没有添加数据之前&#xff0c;可以跑一下这个函数&…...

评一个典型的“数学可视化 + 计算机图形学入门”的优秀案例(C++精灵库3D案例)

这份代码和视频展示了一个非常典型的“数学可视化 计算机图形学入门”的优秀案例。它不仅仅是一段能运行的代码&#xff0c;更是一个将抽象数学公式转化为直观视觉艺术的教学演示。 以下是对该程序及视频的多维度评论&#xff1a; 1. 技术实现与图形学原理 这段代码虽然简短…...

Qwen3字幕系统参数详解:对齐窗口大小、置信度阈值、后处理规则

Qwen3字幕系统参数详解&#xff1a;对齐窗口大小、置信度阈值、后处理规则 1. 系统概述与核心价值 清音刻墨是基于通义千问Qwen3-ForcedAligner核心技术的高精度音视频字幕生成平台。这个系统能够像经验丰富的"司辰官"一样&#xff0c;精确捕捉发音的每一个毫秒&am…...

Phi-3-vision-128k-instruct 代码理解能力展示:解析截图中的复杂算法伪代码

Phi-3-vision-128k-instruct 代码理解能力展示&#xff1a;解析截图中的复杂算法伪代码 1. 引言 最近在GitHub上看到一个有趣的项目&#xff0c;测试了Phi-3-vision-128k-instruct模型对编程相关图像的理解能力。作为一个经常需要阅读算法伪代码的程序员&#xff0c;我对这个…...

文脉定序GPU利用率优化:BGE-Reranker-v2-m3批处理与动态序列长度调优

文脉定序GPU利用率优化&#xff1a;BGE-Reranker-v2-m3批处理与动态序列长度调优 1. 优化背景与价值 在实际部署文脉定序系统时&#xff0c;我们发现GPU利用率存在明显瓶颈。当处理大量检索结果的重排序任务时&#xff0c;传统的逐条处理方式导致GPU计算资源大量闲置&#xf…...

Claude Code + DeepSeek:用自然语言从PRD到上线的打地鼠游戏全流程实录

Claude Code DeepSeek&#xff1a;用自然语言从PRD到上线的打地鼠游戏全流程实录 最近在技术社区里&#xff0c;一个有趣的趋势正在兴起——开发者们开始尝试用自然语言描述需求&#xff0c;然后让AI编程助手自动完成从文档编写到代码生成的全流程。这听起来像科幻小说里的场景…...

DeepSeek API实战:如何用Python脚本绕过Postman直接调用(附完整代码)

DeepSeek API高效调用指南&#xff1a;Python脚本开发实战 在当今快节奏的开发环境中&#xff0c;效率是衡量开发者生产力的关键指标。传统API测试工具如Postman虽然功能强大&#xff0c;但在自动化流程和持续集成场景中往往显得笨重。本文将带你探索一种更轻量、更灵活的解决方…...

gte-base-zh Docker Compose部署:一键编排Xinference+gte-base-zh+WebUI服务栈

gte-base-zh Docker Compose部署&#xff1a;一键编排Xinferencegte-base-zhWebUI服务栈 1. 引言&#xff1a;为什么需要一键部署文本嵌入服务&#xff1f; 如果你正在做智能客服、文档检索或者内容推荐系统&#xff0c;肯定遇到过一个问题&#xff1a;怎么让计算机真正“理解…...

Spring AI实战:从零构建智能聊天与图像生成应用

1. Spring AI初探&#xff1a;你的第一个智能聊天应用 记得第一次接触AI聊天功能时&#xff0c;我盯着那个能对答如流的对话框看了足足十分钟。现在用Spring AI框架&#xff0c;只需要四步就能实现同样的效果。先创建一个标准的Spring Boot项目&#xff0c;这个不用多说&#x…...

OpenClaw备份恢复:Qwen3-VL:30B飞书配置迁移指南

OpenClaw备份恢复&#xff1a;Qwen3-VL:30B飞书配置迁移指南 1. 为什么需要备份恢复OpenClaw配置 上周我的主力开发机突然硬盘故障&#xff0c;导致所有数据丢失。最让我头疼的不是代码仓库——它们都有远程备份&#xff0c;而是那套精心调校的OpenClaw飞书助手配置。这个助手…...