数据结构 之 树习题 力扣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. 二叉树的层序遍历
https://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. 二叉树的锯齿形层序遍历
https://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. 二叉树展开为链表
https://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.创建一个队列记为que,将根节点放入队列。 2.每次从队列中弹出一个节点,记为node。 3.第三步看这个node有没有左孩子,如果有左孩子把左孩子放入到队列中,如果node有右孩子,把右孩子放入到队列中。…...
闭包学习,闭包和高阶函数
面试官反复在前端面试中提出闭包相关的问题,并要求提供代码示例,主要是为了考察以下几点: 1.概念:考察候选人是否真正理解闭包是如何形成的,即当一个函数可以访问并操作其外部作用域中的变量,即使在其外部…...
Linux实战笔记(五) shell
大家好,我是半虹,这篇文章我们介绍一下 shell 1、Shell Shell 通常泛指系统提供给用户的操作界面,是系统内核与用户之间的连接 Shell 这个名字其实还挺形象的,中文翻译是壳,什么的壳呢,自然是系统内核的壳…...
TCP Wrappers 的使用
以ssh为例,每当有ssh的连接请求时,先读取系统管理员所设置的访问控制文件,符合要求,则会把这次连接原封不 动的转给ssh进程,由ssh完成后续工作;如果这次连接发起的ip不符合访问控制文件中的设置,…...
数据结构——lesson11排序之快速排序
💞💞 前言 hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥个人主页&#x…...
Nacos部署(二)Linux部署Nacos2.3.x集群环境
😊 作者: 一恍过去 💖 主页: https://blog.csdn.net/zhuocailing3390 🎊 社区: Java技术栈交流 🎉 主题: Nacos部署(二)Linux部署Nacos2.3.x集群环境 ⏱️…...
RuoYi 自定义字典列表页面编码翻译
“字典数据”单独维护,而不是使用系统自带的字典表,应该如何使用这样的字典信息呢? 系统字典的使用,请参考: 《RuoYi列表页面字典翻译的实现》 https://blog.csdn.net/lxyoucan/article/details/136877238 需求说明…...
GAMES101 学习4
材质和外观 材质 BRDF 漫反射 任何方向的光进来都会被均匀的反射到周围各个不同的方向上去 假设能量守恒,那么 Li Lo,这之后BRDF就 ,就可以定义一个反照率 (Albeo) - ,在(0 - 1࿰…...
Redis中的缓存穿透
缓存穿透 缓存穿透是指客户端请求的数据在缓存中和数据库中都不存在,导致这些请求直接到了数据库上,对数据库造成了巨大的压力,可能造成数据库宕机。 常见的解决方案: 1)缓存无效 key 如果缓存和数据库中都查不到某…...
javaSwing超市收银(txt)
一、简介 超市收银系统是商店管理的重要组成部分,它可以帮助商家高效地进行商品管理、销售记录和结算。本文将介绍如何使用Java Swing开发一个简单的超市收银系统,包括基本功能如登录、修改商品信息、结算等,并利用txt文本作为数据库存储商品…...
Linux 理解文件系统、磁盘结构、软硬链接
目录 一、理解磁盘结构 1、磁盘的物理结构 2、硬件层面理解 3、磁盘的具体物理存储结构 4、进行逻辑抽象 5、磁盘文件的管理 6、创建新文件的过程 二、理解文件系统 1、文件的构成 2、为何选择4KB而非512字节作为基本单位? 3、文件系统的组成 数据块(Data Blocks&a…...
智慧商场数字化创新需要有数字能力帮手
商场和商圈是是促进流通创新、培育新兴消费的载体。很多实体店为适应消费升级需求新变化,加快运用现代信息技术,建设智慧商店,创新消费场景。蚓链运用现代信息技术(互联网、物联网、5G、大数据、人工智能、云计算等)&a…...
JS加密解密之应用如何保存到桌面书签
前言 事情起因是这样的,有个客户解密了一个js,然后又看不懂里边的一些逻辑,想知道它是如何自动拉起谷歌浏览器和如何保存应用到书签的,以及如何下载应用的。继而诞生了这篇文章,讲解一下他的基本原理。 渐进式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 你好,这里是codetrend专栏“高并发编程基础”。 引言 在并发执行任务时,由于资源共享的存在,线程安全成为一个需要考虑的问题。与串行化程序相比,并发执行可以更好地利用CPU计算能力,提高系统的吞吐量…...
八道Python入门级题目及答案详解
前言 介绍Python作为一门流行的编程语言,易学易用的特点。强调通过练习题目来加深对Python语法和编程概念的理解。 题目一:计算两个数的和 描述:编写一个Python程序,计算两个数的和,并输出结果。举例:输…...
Git 的cherry-pick含义
目录 1. cherry-pick的基本概念 2. cherry-pick的使用场景 3. cherry-pick的使用方法 结论 1. cherry-pick的基本概念 git cherry-pick是一个Git命令,它允许你选择一个或多个其他分支上的提交(commits),并将它们复制到你当前的…...
大数据中TopK问题
1.给定100个int数字,在其中找出最大的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+部署+讲解)
前言 博主简介👨🏼⚕️:国内某一线互联网公司全栈工程师👨🏼💻,业余自媒体创作者💻,CSDN博客专家🏆,Java领域优质创作者📕&#x…...
C++经典面试题目(四)
1、请解释const关键字的作用。 在C中,const关键字主要用来表示“不变性”,即被它修饰的东西是不可修改的。它可以用于多种上下文: 修饰基本数据类型变量:声明一个常量,一旦初始化后,其值就不能再更改。 co…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
