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

数据结构 之 树习题 力扣oj(附加思路版)

层序遍历

算法流程:

        1.创建一个队列记为que,将根节点放入队列。

        2.每次从队列中弹出一个节点,记为node。

        3.第三步看这个node有没有左孩子,如果有左孩子把左孩子放入到队列中,如果node有右孩子,把右孩子放入到队列中。

        4.重复步骤二和步骤三,直到队列为空。

相关函数和知识: 

#include"Tree.h"
int main()
{vector<int>vec;//二维数组就是一维数组中的元素是一维数组vector<vector<int>>vec1;vec1.push_back(vec);//排序函数sort(vec.begin(), vec.end());//从小到大排序sort(vec.rbegin(), vec.rend());//从大到小排序reverse(vec.begin(), vec.end());//反转数组
}

二叉树的层序遍历 

102. 二叉树的层序遍历icon-default.png?t=N7T8https://leetcode.cn/problems/binary-tree-level-order-traversal/

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。

思路

         通过维护一个队列实现了对二叉树的层序遍历。首先,根节点入队。然后,当队列不为空时,循环执行:遍历当前队列中的所有节点,将它们的值收集到一个二维向量中,并将它们的非空左右子节点依次入队。每完成一层的遍历,就将这一层的向量添加到结果向量中,直到遍历完所有层。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if(root==nullptr) return {};queue<TreeNode*>que;que.push(root);vector<vector<int>>res;while(!que.empty()){vector<int>vec;int n=que.size();for(int i=0;i<n;i++){ TreeNode*front=que.front();que.pop();vec.push_back(front->val);if(front->left)que.push(front->left);if(front->right)que.push(front->right);}res.push_back(vec);}return res;}
};

二叉树的锯齿形层序遍历 

103. 二叉树的锯齿形层序遍历icon-default.png?t=N7T8https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

        给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

思路

          这段代码实现了二叉树的锯齿形层序遍历。它使用了队列来进行层序遍历,同时通过一个布尔变量 flag 来标记是否需要反转当前层的节点值顺序。每次遍历一层时,先将该层的节点值存入一个临时的 vector 中,然后根据 flag 变量的值决定是否需要反转该 vector,最后将其加入结果 vector 中。这样可以实现从左向右和从右向左交替进行层序遍历。

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if(root==nullptr) return {};vector<vector<int>>res;queue<TreeNode*>que;que.push(root);bool flag=false;while(!que.empty()){vector<int>vec;//写在循环里会每次都清空int n=que.size();for(int i=0;i<n;i++){TreeNode*front=que.front();que.pop();vec.push_back(front->val);if(front->left) que.push(front->left);if(front->right) que.push(front->right);}if (flag) reverse(vec.begin(), vec.end());flag=!flag;res.push_back(vec);}return res;}
};

先序遍历

Preorder算法流程:

        1.先申请一个栈,记为stk。

        2.然后将根节点压入stk 中。

        3.每次从stk 中弹出栈顶节点,记为cur,然后打印cur的值。如果cur的右子节点不为空,将cur的右子树压入stk 中。如果cur的左子树不为空,将cur的左子节点压入stk 中。不断重复次步骤3直到stk为空循环结束。


二叉树展开为链表 

114. 二叉树展开为链表icon-default.png?t=N7T8https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/

提示

给你二叉树的根结点 root ,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

思路

        通过先序遍历二叉树的方式,将每个节点按顺序连接到单链表中。利用栈来模拟递归的过程,先将根节点入栈,然后不断弹出栈顶节点,将其右子节点和左子节点依次入栈,同时将当前节点连接到链表中。

class Solution {
public:void flatten(TreeNode* root) {if(root==nullptr) return ;stack<TreeNode*>stk;stk.push(root);TreeNode *H=new TreeNode(),*T=H;//因为头节点不知道拼在哪 故创建一个虚头节点while (!stk.empty()){TreeNode* top = stk.top();stk.pop();T->right=top;T->left=nullptr;T=T->right;if (top->right) stk.push(top->right);//因为栈是后进先出 所以右子树先进if (top->left) stk.push(top->left);}delete H;}
};

相关文章:

数据结构 之 树习题 力扣oj(附加思路版)

层序遍历 算法流程: 1&#xff0e;创建一个队列记为que,将根节点放入队列。 2.每次从队列中弹出一个节点&#xff0c;记为node。 3.第三步看这个node有没有左孩子&#xff0c;如果有左孩子把左孩子放入到队列中&#xff0c;如果node有右孩子&#xff0c;把右孩子放入到队列中。…...

闭包学习,闭包和高阶函数

面试官反复在前端面试中提出闭包相关的问题&#xff0c;并要求提供代码示例&#xff0c;主要是为了考察以下几点&#xff1a; 1.概念&#xff1a;考察候选人是否真正理解闭包是如何形成的&#xff0c;即当一个函数可以访问并操作其外部作用域中的变量&#xff0c;即使在其外部…...

Linux实战笔记(五) shell

大家好&#xff0c;我是半虹&#xff0c;这篇文章我们介绍一下 shell 1、Shell Shell 通常泛指系统提供给用户的操作界面&#xff0c;是系统内核与用户之间的连接 Shell 这个名字其实还挺形象的&#xff0c;中文翻译是壳&#xff0c;什么的壳呢&#xff0c;自然是系统内核的壳…...

TCP Wrappers 的使用

以ssh为例&#xff0c;每当有ssh的连接请求时&#xff0c;先读取系统管理员所设置的访问控制文件&#xff0c;符合要求&#xff0c;则会把这次连接原封不 动的转给ssh进程&#xff0c;由ssh完成后续工作&#xff1b;如果这次连接发起的ip不符合访问控制文件中的设置&#xff0c…...

数据结构——lesson11排序之快速排序

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…...

Nacos部署(二)Linux部署Nacos2.3.x集群环境

&#x1f60a; 作者&#xff1a; 一恍过去 &#x1f496; 主页&#xff1a; https://blog.csdn.net/zhuocailing3390 &#x1f38a; 社区&#xff1a; Java技术栈交流 &#x1f389; 主题&#xff1a; Nacos部署&#xff08;二&#xff09;Linux部署Nacos2.3.x集群环境 ⏱️…...

RuoYi 自定义字典列表页面编码翻译

“字典数据”单独维护&#xff0c;而不是使用系统自带的字典表&#xff0c;应该如何使用这样的字典信息呢&#xff1f; 系统字典的使用&#xff0c;请参考&#xff1a; 《RuoYi列表页面字典翻译的实现》 https://blog.csdn.net/lxyoucan/article/details/136877238 需求说明…...

GAMES101 学习4

材质和外观 材质 BRDF 漫反射 任何方向的光进来都会被均匀的反射到周围各个不同的方向上去 假设能量守恒&#xff0c;那么 Li Lo&#xff0c;这之后BRDF就 &#xff0c;就可以定义一个反照率 &#xff08;Albeo&#xff09; - &#xff0c;在&#xff08;0 - 1&#xff0…...

Redis中的缓存穿透

缓存穿透 缓存穿透是指客户端请求的数据在缓存中和数据库中都不存在&#xff0c;导致这些请求直接到了数据库上&#xff0c;对数据库造成了巨大的压力&#xff0c;可能造成数据库宕机。 常见的解决方案&#xff1a; 1&#xff09;缓存无效 key 如果缓存和数据库中都查不到某…...

javaSwing超市收银(txt)

一、简介 超市收银系统是商店管理的重要组成部分&#xff0c;它可以帮助商家高效地进行商品管理、销售记录和结算。本文将介绍如何使用Java Swing开发一个简单的超市收银系统&#xff0c;包括基本功能如登录、修改商品信息、结算等&#xff0c;并利用txt文本作为数据库存储商品…...

Linux 理解文件系统、磁盘结构、软硬链接

目录 一、理解磁盘结构 1、磁盘的物理结构 2、硬件层面理解 3、磁盘的具体物理存储结构 4、进行逻辑抽象 5、磁盘文件的管理 6、创建新文件的过程 二、理解文件系统 1、文件的构成 2、为何选择4KB而非512字节作为基本单位? 3、文件系统的组成 数据块&#xff08;Data Blocks&a…...

智慧商场数字化创新需要有数字能力帮手

商场和商圈是是促进流通创新、培育新兴消费的载体。很多实体店为适应消费升级需求新变化&#xff0c;加快运用现代信息技术&#xff0c;建设智慧商店&#xff0c;创新消费场景。蚓链运用现代信息技术&#xff08;互联网、物联网、5G、大数据、人工智能、云计算等&#xff09;&a…...

JS加密解密之应用如何保存到桌面书签

前言 事情起因是这样的&#xff0c;有个客户解密了一个js&#xff0c;然后又看不懂里边的一些逻辑&#xff0c;想知道它是如何自动拉起谷歌浏览器和如何保存应用到书签的&#xff0c;以及如何下载应用的。继而诞生了这篇文章&#xff0c;讲解一下他的基本原理。 渐进式Web应用…...

线上linux服务器升级nginx

一个nginx版本空包 一个pcre文件 一个zlib文件 ./configure配置文件 make编译 make install复制所有文件到nginx 如果nginx -v无版本号 检查环境变量cat /etc/profile 编辑 环境变量vi /etc/profile 按i进入编辑模式 按esc进入查看模式 因为path中并未使用%JAVA_HOME%字样…...

使用JDK提供的常用工具在多线程编写线程安全和数据同步的程序

题图来自APOD 你好&#xff0c;这里是codetrend专栏“高并发编程基础”。 引言 在并发执行任务时&#xff0c;由于资源共享的存在&#xff0c;线程安全成为一个需要考虑的问题。与串行化程序相比&#xff0c;并发执行可以更好地利用CPU计算能力&#xff0c;提高系统的吞吐量…...

八道Python入门级题目及答案详解

前言 介绍Python作为一门流行的编程语言&#xff0c;易学易用的特点。强调通过练习题目来加深对Python语法和编程概念的理解。 题目一&#xff1a;计算两个数的和 描述&#xff1a;编写一个Python程序&#xff0c;计算两个数的和&#xff0c;并输出结果。举例&#xff1a;输…...

Git 的cherry-pick含义

目录 1. cherry-pick的基本概念 2. cherry-pick的使用场景 3. cherry-pick的使用方法 结论 1. cherry-pick的基本概念 git cherry-pick是一个Git命令&#xff0c;它允许你选择一个或多个其他分支上的提交&#xff08;commits&#xff09;&#xff0c;并将它们复制到你当前的…...

大数据中TopK问题

1.给定100个int数字&#xff0c;在其中找出最大的10个; import java.util.PriorityQueue;public class Main {public static void main(String[] args) {final int topK 3;int[] vec {4, 1, 5, 8, 7, 2, 3, 0, 6, 9};PriorityQueue<Integer> pq new PriorityQueue<…...

基于SpringBoot+MyBatis+Vue的电商智慧仓储管理系统的设计与实现(源码+LW+部署+讲解)

前言 博主简介&#x1f468;&#x1f3fc;‍⚕️&#xff1a;国内某一线互联网公司全栈工程师&#x1f468;&#x1f3fc;‍&#x1f4bb;&#xff0c;业余自媒体创作者&#x1f4bb;&#xff0c;CSDN博客专家&#x1f3c6;&#xff0c;Java领域优质创作者&#x1f4d5;&#x…...

C++经典面试题目(四)

1、请解释const关键字的作用。 在C中&#xff0c;const关键字主要用来表示“不变性”&#xff0c;即被它修饰的东西是不可修改的。它可以用于多种上下文&#xff1a; 修饰基本数据类型变量&#xff1a;声明一个常量&#xff0c;一旦初始化后&#xff0c;其值就不能再更改。 co…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...