【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;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/465683.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

dns服务器配置

主服务器 1.挂载点 mount /dev/sr0 /mnt 2.防火墙关闭 systemctl stop firewalld setenforce 0 3.下载bind软件 dnf install bind -y 4.进行正向解析配置 vim /etc/named.conf options { listen-on port 53 { 192.168.92.128; }; directo…

stable diffusion图生图

本节内容&#xff0c;给大家带来的是stable diffusion的图生图课程&#xff0c;我们在midjourney的课程中有学习过midjourney的图生图功能&#xff0c;即使用垫图的方式来引导AI绘制图片。图生图是AI绘图程序一个非常重要的功能&#xff0c;stable diffusion同样提供了类似的功…

论文阅读笔记:DRCT: Saving Image Super-Resolution away from Information Bottleneck

论文阅读笔记&#xff1a;DRCT: Saving Image Super-Resolution away from Information Bottleneck 1 背景1.1 问题1.2 本文提出的方法 2 创新点3 方法4 模块4.1 问题描述4.2 深度特征提取模块4.3 同任务渐进式训练策略 5 效果5.1 和SOTA方法对比 论文&#xff1a;https://arxi…

一周内从0到1开发一款 AR眼镜 相机应用?

目录 1. &#x1f4c2; 前言 2. &#x1f4a0; 任务拆分 2.1 产品需求拆分 2.2 开发工作拆分 3. &#x1f531; 开发实现 3.1 代码目录截图 3.2 app 模块 3.3 middleware 模块 3.4 portal 模块 4. ⚛️ 拍照与录像 4.1 前滑后滑统一处理 4.2 初始化 View 以及 Came…

【论文精读】LPT: Long-tailed prompt tuning for image classification

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;论文精读_十二月的猫的博客-CSDN博客 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 1. 摘要 2. …

《重学Java设计模式》之 建造者模式

建造者模式所完成的内容就是通过将多个简单对象通过一步步的组装构建出一个复杂对象的过程 模拟装修公司对于设计出一些套餐装修服务的场景。 很多装修公司都会给出自家的套餐服务&#xff0c;一般有&#xff1b;豪华、轻奢、简约等&#xff0c;这些套餐的后面是不同的商品的…

Android Framework AMS(12)广播组件分析-3(广播发送流程解读)

该系列文章总纲链接&#xff1a;专题总纲目录 Android Framework 总纲 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;本章节主要解读广播组件的广播发送过程。关注思维导图中左上侧部分即可。 有了前面广播组件 注册和注销程分析的基础&#xff0c;基于此&#xff…

MongoDB笔记02-MongoDB基本常用命令

文章目录 一、前言二、数据库操作2.1 选择和创建数据库2.2 数据库的删除 3 集合操作3.1 集合的显式创建3.2 集合的隐式创建3.3 集合的删除 四、文档基本CRUD4.1 文档的插入4.1.1 单个文档插入4.1.2 批量插入 4.2 文档的基本查询4.2.1 查询所有4.2.2 投影查询&#xff08;Projec…

MySQL基础-单表查询

语法 select [distinct] 列名1&#xff0c;列名2 as 别名... from数据表名 where组前筛选 group by分组字段 having组后筛选 order by排序的列 [asc | desc] limit 起始索引&#xff0c;数据条数 测试数据 # 建测试表 create table products (id int primary key a…

【pycharm jupyter】远程开发 启动报错

报错信息 upyter server process exited with code 1 ServerApp] A _jupyter_server_extension_points function was not found in jupyter_lsp. Instead, a _jupyter_server_extension_paths function was found and will be used for now. This function name will be depre…

CPU Study - Instructions Fetch

参考来源&#xff1a;《超标量处理器设计》—— 姚永斌 N-Way CPU 取指问题 如果CPU可以在每个周期内同时解码N条指令&#xff0c;则此类CPU为N-Way超标量处理器。 N-Way超标量处理器需要每个周期从I-Cache中至少取得N条指令&#xff0c;这N条指令成为一组Fetch Group。 为了…

掌握 PyQt5:从零开始的桌面应用开发

PyQT5——图形化界面 文章目录 PyQT5——图形化界面集成化图形界面工具为什么使用 \$ProjectFileDir$?示例场景其他 Varaiablespyuic参数解释整体含义示例使用PyQt5和pyuic 创建pyqt5的程序创建一个窗口app.exec\_()和sys.exit(app.exec_())的区别1. app.exec_()2. sys.exit(a…

论文阅读笔记:Image Processing GNN: Breaking Rigidity in Super-Resolution

论文阅读笔记&#xff1a;Image Processing GNN: Breaking Rigidity in Super-Resolution 1 背景2 创新点3 方法4 模块4.1 以往SR模型的刚性4.2 图构建4.2.1 度灵活性4.2.2 像素节点灵活性4.2.3 空间灵活性 4.3 图聚合4.4 多尺度图聚合模块MGB4.5 图聚合层GAL 5 效果5.1 和SOTA…

PMP–一、二、三模、冲刺–分类–7.成本管理–技巧–挣值分析

文章目录 技巧一模7.成本管理--4.控制成本--数据分析--挣值分析--进度绩效指数&#xff08;SPI&#xff09;是测量进度效率的一种指标&#xff0c;表示为挣值与计划价值之比&#xff0c;反映了项目团队完成工作的效率。 当 SPI小于 1.0 时&#xff0c;说明已完成的工作量未达到…

保姆级教程!!教你通过【Pycharm远程】连接服务器运行项目代码

小罗碎碎念 这篇文章主要解决一个问题——我有服务器&#xff0c;但是不知道怎么拿来写代码&#xff0c;跑深度学习项目。确实&#xff0c;玩深度学习的成本比较高&#xff0c;无论是前期的学习成本&#xff0c;还是你需要具备的硬件成本&#xff0c;都是拦路虎。小罗没有办法…

成绩管理系统软件体系结构设计

成绩管理系统软件体系结构设计 文档简介 1.1 目的 1.2 范围 1.3 定义、首字母缩写词和缩略语 1.4参考资料 1.5 概述体系结构表示方式软件体系结构的目标和约束 3.1 结构清晰 3.2 支持外包开发 3.3 可扩展性 3.4 系统安全性 3.5 可移植性 4体系结构模式逻辑视图进程视图…

单臂路由实现不同VLAN之间设备通信

转载请注明出处 本实验为单臂路由配置&#xff0c;目的为让不同VLAN之间的设备能够互相通信。 1.首先&#xff0c;按照要求配置两个pc的ip地址&#xff0c;以pc0为例子&#xff1a; 2在交换机创建vlan10和vlan20 3.划分vlan&#xff0c;pc0为vlan10的设备&#xff0c;pc1为vla…

机器学习(三)——决策树(附核心思想、重要算法、概念(信息熵、基尼指数、剪枝处理)及Python源码)

目录 关于1 基本流程2 划分属性的选择2.1 方法一&#xff1a;依据信息增益选择2.2 方法二&#xff1a;依据增益率选择2.3 方法三&#xff1a;依据基尼指数选择 3 剪枝处理&#xff1a;防止过拟合3.1 预剪枝3.2 后剪枝 4 连续与缺失值4.1 连续值处理4.2 缺失值处理 5 多变量决策…

Ubuntu和Debian系列的Release默认shell解释器变更

Debian 12 Bookworm 和 Ubuntu 24.04 中默认的 shell 解释器已经由 bash 变更为了 dash 。 这个变化对于我们直接在 CLI 上执行 Linux command 无影响&#xff0c;但对于执行shell解释性程序有影响&#xff0c;已知 bash 中的 变量正规表达式 &#xff08;如 ${GIT_COMMIT:0:8…

ReLU6替换ReLU为什么可以增强硬件效率?

ReLU6&#xff08;Rectified Linear Unit 6&#xff09;是ReLU的一种变体&#xff0c;它在ReLU的基础上增加了一个上限值6&#xff0c;即输出范围被限制在[0, 6]之间。 这种变化在硬件实现中可以带来以下几个方面的效率提升&#xff1a; 1. 数据表示的简化 ReLU的输出范围是[…