【数据结构_12】二叉树(4)
一、二叉树的层序遍历
思路:可以按照先序的方式来遍历这个树,递归的时候,给递归方法,加上辅助的参数,level表示当前层数,递归过程中,根据level的值,决定当前整个节点要放到哪个list中。这个题目中,是通过二维list表示结果的,list中的[0]的元素就是根节点,如果把根节点视为第 0 层,此时的level就是和下标对应上了,如果把根节点视为第一层,就需要把level-1再作为下标。
代码段:
public void levelOrderHelper(TreeNode root, int k,List<List<Integer>> result){if(root == null){return ;}//当前level这一层的List是否被创建出来了if(result.size() == k){result.add(new ArrayList<>());}//取出当前元素,添加到第level行中List<Integer> curRow = result.get(k);curRow.add(root.val);//递归处理左右子树levelOrderHelper(root.left,k+1,result);levelOrderHelper(root.right,k+1,result);}public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if(root == null){return result ;}levelOrderHelper(root,0,result);return result;}
二、二叉树的最近公共祖先
从根节点到达这个指定节点,路径上经过的所有节点,都可以视为这个节点的祖先。所谓的公共祖先,意味着公共祖先子树中级同时包含了这两个节点。比如,确认了公共祖先这个节点,确实包含了p和q这两个节点,也就意味着p和q就可能出现在三个位置:
1.p/q是根节点
2.p/q存在于左子树
3.p/q存在于右子树
如果是最近的公共祖先,意味着p和q就会分布在上述三种情况的两种之中
其他的公共祖先,意味着p和q都是分布在上述三种情况的一种之中
代码的整体思路:
从根节点出发,递归地针对每个子树进行茶渣p和q的操作,对于任意一个节点,在根节点中查找p和q,在左子树中查找p和q,在右子树中查找p和q。针对上述三个范围的查找,分别使用int变量来表示查找结果.如果找到p或者q认为返回值为1;如果没找到p或者q返回值为0.
再将上述三个结果进行相加,如果
结果为0,意味着当前节点不是p和q的祖先
如果结果为1,意味着当前节点可能是p或者q的祖先
如果结果为2,意味着当前节点一定是p和q的最近公共祖先。
代码段如下:
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {private TreeNode lca = null;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {lca = null;if(root == null){return null;}if(root == p || root == q){return root;}//需要使用一个辅助方法进行递归,完成上述的逻辑find(root,p,q);return lca;}public int find(TreeNode root,TreeNode p,TreeNode q){if(root == null){return 0;}//针对根节点查找返回的0/1int mid = (root == p || root ==q )?1:0;//针对左子树查找返回的0/1int left = find(root.left,p,q);//针对右子树查找返回的 0 / 1int right = find(root.right,p,q);if(mid + right + left ==2){//说明root就是最近的公共祖先//最近公共祖先只有一个,但是find方法是递归过程中找到的//如何把这个公共祖先返回到上一个方法中去呢?lca = root;}return mid + right + left > 0 ? 1:0;}
}
这道题的一些难点:
1.理解公共祖先和最近公共祖先
2.分析出公共祖先和最近公共祖先的差异(代码来描述);三个范围中,其中的两个范围分别找到了p和q,就是最近公共祖先
3.编写代码,通过三个 0 / 1 这样的int值相加,看是否为2
4.如何方便简单地拿到返回值
三、根据前序遍历和中序遍历序列构造二叉树
关键结论:
1.先序的第一个元素,就是根节点
2.先序中,根节点左侧的就是左子树的中序;根节点右侧的就是右子树的中西
3.先序中,知道了哪些节点是左子树,哪些节点是右子树之后,此时,先序中对应的序列,也就是左右子树的先序结果
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {//首先创建一个index来表示当前去到了preorder中的哪个元素private int index = 0;public TreeNode buildTree(int[] preorder, int[] inorder) {index =0;//创建一个方法来辅助创建树return buildTreeHelper(preorder,inorder,0, inorder.length);}public TreeNode buildTreeHelper(int[] preorder,int[] inorder, int inleft ,int inright){if(inleft >= inright){//给定的区间是空区间,意味着对应空树return null;}if(index >= preorder.length){//说明已经遍历完了preorder这个数组return null;}//取出index对应的元素,构造出当前的节点TreeNode root = new TreeNode(preorder[index]);index++;//接下来要找到root在中序序列的位置int pos = findPos(inorder,inleft,inright,root.val);//再递归左子树,递归右子树root.left =buildTreeHelper(preorder,inorder,inleft,pos);root.right =buildTreeHelper(preorder,inorder,pos+1,inright);return root;}public int findPos(int[] inorder,int inleft,int inright,int val){//循环遍历for(int i=inleft;i<inright;i++){if(inorder[i]== val){return i;}}return -1;}
}
四、从中序与后序遍历序列构造二叉树
相关文章:
【数据结构_12】二叉树(4)
一、二叉树的层序遍历 思路:可以按照先序的方式来遍历这个树,递归的时候,给递归方法,加上辅助的参数,level表示当前层数,递归过程中,根据level的值,决定当前整个节点要放到哪个list中…...
HCIA-Datacom高阶:vlan、vlanif、单臂路由、静态路由、ospf综合实验
本实验拓扑图如下:实验包含 AR1、AR2、AR3 路由器,LSW1(三层交换机)、LSW2、LSW3 交换机,以及 PC1-4 和 Server1。AR1 与 LSW2 通过单臂路由连接,AR2 与 AR3、LSW1 构成 OSPF 网络,AR1 与 AR2 间…...
HTTP 1.0 和 2.0 的区别
HTTP 1.0 和 2.0 的核心区别体现在性能优化、协议设计和功能扩展上,以下是具体对比: 一、核心区别对比 特性HTTP 1.0HTTP 2.0连接方式非持久连接(默认每次请求新建 TCP 连接)持久连接(默认保持连接,可复用…...
如何一键批量删除多个 Word 文档中的页眉和页脚
在工作中,许多 Word 文档的页眉页脚中包含公司名称、Logo、电话等信息,用于对外宣传。但有时我们需要批量删除这些页眉页脚信息,尤其当信息有误时,手动逐个删除会增加工作量,导致效率低下。本文将介绍一种便捷的方法&a…...
关于编译树莓派内核系统的总结
1.首先获取官方的内核系统源码: 然后在源码根目录执行命令: 🌟ARCHarm64 CROSS_COMPILEaarch64-linux-gnu- KERNELkernel8 make bcm2712_defconfig (注意这里的是树莓派5的64位的) 🌟ARCHarm CROSS_COM…...
AIGC赋能插画创作:技术解析与代码实战详解
文章目录 一、技术架构深度解析二、代码实战:构建AIGC插画生成器1. 环境配置与依赖安装2. 模型加载与文本提示词构建3. 图像生成与参数调优4. 风格迁移与多模型融合 三、进阶技巧:参数调优与效果增强四、应用场景代码示例1. 游戏角色设计2. 广告海报生成…...
平衡二叉树(leetcode刷题)
题目描述: 给定一个二叉树,判断它是否是 平衡二叉树 (平衡二叉树 是指该树所有节点的左右子树的高度相差不超过 1。) 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:true示例 2࿱…...
【数据结构 · 初阶】- 带环链表
目录 一.基本结构 二.判断一个单链表带不带环 三.2个问题 1.为什么 slow 走 1 步,fast 走 2 步,他们会相遇,会不会错过?请证明。 2.为什么 slow 走 1 步,fast 走 X 步 ( X > 3 ),他们会相遇&#x…...
ClickHouse简介
OLAP与ClickHouse的定位 OLAP的核心概念 OLTP:服务于高并发、低延迟的短事务操作(如银行转账、订单支付),强调数据的增删改查(CRUD)和事务一致性(ACID)。 OLAP:专注于大…...
强制重装及验证onnxruntime-gpu是否正确工作
#工作记录 我们经常会遇到明明安装了onnxruntime-gpu或onnxruntime后,无法正常使用的情况。 一、强制重新安装 onnxruntime-gpu 及其依赖 # 强制重新安装 onnxruntime-gpu 及其依赖 pip install --force-reinstall --no-cache-dir onnxruntime-gpu1.18.0 --extra…...
分布自定义shell脚本(详写)附带全代码
涉及知识全排列 常见指令 小知识点 操作系统 什么是进程 进程控制 步骤 1:项目准备 在开始编写代码之前,你需要创建一个新的项目文件夹,并在其中创建一个 .cpp 文件,例如 my_shell.cpp。同时,确保你已经安装了 C…...
windows拷贝文件脚本
1、新建脚本文件xxx.bat,名字任意,后缀未.bat即可,将以下内容拷贝进去,修改src和des为自己文件的目录即可。 echo off :: 设置字符集为UTF-8,命令窗口能正确显示中文字符。 chcp 65001 rem 读取当前目录并进入当前目…...
Arduino编译和烧录STM32——基于J-link SWD模式
一、安装Stm32 Arduino支持 在arduino中添加stm32的开发板地址:https://github.com/stm32duino/BoardManagerFiles/raw/main/package_stmicroelectronics_index.json 安装stm32开发板支持 二、安装STM32CubeProgrammer 从stm32网站中安装:https://ww…...
Java表达式2.0
1 .数据类型转换 自动类型转换的规则 自动类型转换遵循一定的规则,这些规则确保了转换的合理性和安全性。以下是自动类型转换的主要规则: 容量小的类型自动转换为容量大的类型 Java中,数据类型的容量从小到大依次为:byte → shor…...
【概率论,算法】排列的峰值期望
Surtr1 的珂学难题 题目链接:https://ac.nowcoder.com/acm/contest/107965/E 给定一个长度为 n n n 的排列 p p p,排列中任一位置如果满足以下条件,则称该位置为 峰值: 位置 1:若存在元素,满足 p [ 1 ] > p […...
清理C盘组合拳:最高释放空间80GB+
分享一套系统化的C盘清理方案,涵盖从基础清理到深度优化的8个关键步骤,结合安全性与效率,可快速释放5-50GB空间: 一、精准定位空间占用源(必备工具) 空间可视化分析 使用 TreeSize Free 或 WizTree 扫描C…...
容器中的对象切片问题
C 容器(如 std::vector、std::list 等) 通常存储对象的副本,而非指向对象的指针。因此,当与继承结合使用时,可能导致 切片(Object Slicing) 问题,即仅存储基类部分,丢失派…...
SpringBoot编写单元测试
pom.xml引入单元测试的坐标 <!--单元测试坐标--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-test</artifactId><scope>test</scope></dependency>编写单元测试类 测试类…...
二、在springboot 中使用 AIService
在上一篇文章中,我们介绍了如何使用langchain4j实现简单的问答功能,本篇文章我们将介绍如何在springboot中使用AIService。 1.实现原理 先看下AiService注解所在的依赖langchain4j-spring-boot-starter中包含什么内容: 1.1 event.AiServi…...
拼多多面经,暑期实习Java一面
项目中的设计模式 mysql连接过程,索引,分库分表场景,路由策略 redis使用场景,分片集群怎么搭建与路由,数据一致性 分布式锁怎么用的,具体使用参数 线程池怎么用的,过程 sql having 分布式事务 如…...
Function calling LLMs 的 MCP:AI开发的双剑合璧
🧠 向所有学习者致敬! “学习不是装满一桶水,而是点燃一把火。” —— 叶芝 我的博客主页: https://lizheng.blog.csdn.net 🌐 欢迎点击加入AI人工智能社区! 🚀 让我们一起努力,共创AI未来! 🚀 在 MCPs 成为主流(或者像现在这样火得一塌糊涂)之前,大多数 AI …...
数字系统与编码
1. 数字系统(Number Systems) 1.1 常见数字系统 系统基数符号集示例应用场景二进制20, 11010计算机底层电路、数据存储八进制80-717Unix文件权限(如chmod 755)十进制100-942日常计算十六进制160-9, A-F0x1F内存地址、颜色编码&a…...
Pytorch实战
1、安装 安装 conda, Python工具大全,方便管理多个 Python 环境,必须选择跟自己环境配套的版本。 https://www.anaconda.com 网速慢的,可以参考国内源,也可以去这里看看: torch PyPI Index of /anaconda/miniconda…...
如何高效利用呼叫中心系统和AI语音机器人
要更好地使用呼叫中心系统和语音机器人,需要结合两者的优势,实现自动化、智能化、高效率的客户服务与业务运营。以下是优化策略和具体实践方法: 一、呼叫中心系统优化 1. 智能路由与IVR优化 智能ACD(自动呼叫分配) …...
LeetCode[232]用栈实现队列
思路: 一道很简单的题,就是栈是先进后出,队列是先进先出,用两个栈底相互对着,这样一个队列就产生了,右栈为空的情况,左栈栈底就是队首元素,所以我们需要将左栈全部压入右栈ÿ…...
using用法整理
using 的极简新手教程,用最直白的语言和代码解释: 美图美图 一、核心作用:给类型起别名 目的:让复杂类型名变短、变好记。 例子: // 原名:std::vector<std::string> // 起个别名就叫 StringList…...
《猎豹夕阳》
年少时很喜欢的一篇文章,曾和挚友一遍又一遍的记诵,今天又偶然遇到他,转载如下: 我第一次见到它,是在风雪的夜里。我不会抱怨这种天气,因为我是个优秀的登山探险者,我必须在这种天气下工作。我…...
【AI训练环境搭建】在Windows11上搭建WSL2+Ubuntu22.04+Tensorflow+GPU机器学习训练环境
一、安装Ubuntu 拿到该文件Ubuntu-22.04.tar 通过wsl导入该虚拟机镜像,然后查看wsl虚拟机列表。 wsl --import Ubuntu-22.04-tensorflow D:\wsl-data\Ubuntu-22.04-tensorflow D:\wsl-data\temp\Ubuntu-22.04.tarwsl -l 进入虚拟机 wsl -d Ubuntu-22.04-tensorfl…...
如何轻松实现用户充值系统的API自动化测试
在现代软件开发中,API(应用程序编程接口)作为连接不同系统和模块的关键组件,其重要性日益凸显。随着软件应用的互联性不断增强,API的数量和复杂度也在不断增加。传统的API测试方法面临着诸多挑战: 1.手动测…...
Python 一等函数( 高阶函数)
高阶函数 接受函数为参数,或者把函数作为结果返回的函数是高阶函数(higherorder function)。map 函数就是一例,如示例 5-2 所示。此外,内置函 数 sorted 也是:可选的 key 参数用于提供一个函数,…...
用于手部康复设备的TinyML语音分类嵌入式人工智能模块
论文标题 英文标题:TinyML Speech Classification Embedded AI Module for Hand Rehabilitation Device 中文标题:用于手部康复设备的 TinyML 语音分类嵌入式人工智能模块 作者信息 Arkorn Numsomran:Triam Udom Suksa Pattanakarn Suvarna…...
【HarmonyOS 5】VisionKit人脸活体检测详解
【HarmonyOS 5】VisionKit人脸活体检测详解 一、VisionKit人脸活体检测是什么? VisionKit是HamronyOS提供的场景化视觉服务工具包。 华为将常见的解决方案,通常需要三方应用使用SDK进行集成。华为以Kit的形式集成在HarmoyOS系统中,方便三方…...
Linux操作系统--进程的创建和终止
目录 1.进程创建 1.1fork()函数初识 1.2写时拷贝 1. 提升系统效率 2. 隔离错误影响 3. 支持并行计算 2.进程终止: 2.1进程退出场景: 2.2进程常见退出方法: 2.3_exit()系统调用接口 2.4exit函数 2.5return退出 1.进程创建 1.1for…...
算法分析传输加密数据格式密文存储代码混淆逆向保护
代码混淆 一.基本概念java的bytecode很容易通过JAD等反编译工具还原出源代码。这样势必不满足安全的定义。如何一定程度上保护需要防止被反编译的源代码呢?混淆(obfuscate)技术注意:用obfuscate防盗版是根本不可能,连汇…...
从事计算机视觉需要掌握哪些知识
目录 基础数学知识 计算机科学基础 传统计算机视觉知识 机器学习与深度学习知识 其他知识 计算机视觉是一门让计算机从图像或视频中获取有意义信息的跨学科领域,从事该领域需要掌握多方面的知识,以下详细介绍: 基础数学知识 线性代数 &…...
Android Studio 中 Drawable 详细全解
文章目录 一、Drawable 概述二、Drawable 类型详解1. 位图 Drawable (BitmapDrawable)2. 矢量 Drawable (VectorDrawable)3. 形状 Drawable (ShapeDrawable)4. 图层 Drawable (LayerDrawable)5. 状态列表 Drawable (StateListDrawable)6. 级别列表 Drawable (LevelListDrawable…...
【实战中提升自己】内网安全部署之端口隔离与MAC地址认证
1 1拓扑 「模拟器、工具合集」复制整段内容 链接:https://docs.qq.com/sheet/DV0xxTmFDRFVoY1dQ?tab7ulgil 1 端口隔离技术部署 [boss]port-group 1 [boss-port-group-1]port-isolate enable 说明:这里有几个地方不需要部署…...
Linux 420 find stat touch tree scp crontab
准备安装CentOSstream https://blog.csdn.net/s_alted/article/details/117739735 官网 CentOS 9 “Couldn’t open file /mnt/repodata/repomd.xml” deepseek 下载成功 树状 另一台虚拟机...
基于 Vue3 + ECharts + GeoJson 实现区域地图钻取功能详解
文章目录 前言一、实现步骤1. 项目初始化2. 准备GeoJson数据3. 创建地图组件4. 创建主页面组件5. 使用组件 二、功能亮点三、性能优化建议四、常见问题解决五、结语六、实战demo七、资源下载 前言 在数据可视化领域,地图展示是一种非常直观的表现形式。而地图钻取&…...
算法题(129):二维前缀和
审题: 本题需要我们将q组矩阵的和打印出来 思路: 方法一:二维前缀和 由于本题使用暴力的模拟方法运行次数高达1e11,会超时,所以我们采用运行次数在1e6的二维前缀和来解题 第一步:前缀和的求法 x i…...
NEAT 算法解决 Lunar Lander 问题:从理论到实践
NEAT 算法解决 Lunar Lander 问题:从理论到实践 0. 前言1. 定义环境2. 配置 NEAT3. 解决 Lunar lander 问题小结系列链接0. 前言 在使用 NEAT 解决强化学习问题一节所用的方法只适用于较简单的强化学习 (reinforcement learning, RL) 环境。在更复杂的环境中使用同样的进化解…...
Arduino示例代码讲解:Project 07 - Keyboard 键盘
Arduino示例代码讲解:Project 07 - Keyboard 键盘 Project 07 - Keyboard 键盘程序功能概述功能:硬件要求:输出:代码结构全局变量`setup()` 函数`loop()` 函数读取电位器值:打印电位器值:播放音调:运行过程注意事项Project 07 - Keyboard 键盘 /*Arduino Starter Kit e…...
4.凸包-Graham Scan
Graham Scan:Algorithm Preprocessing 根据角度进行排序 Graham Scan 例子 例2 Graham Scan:Correctness Left Turn/right Trun 下一个点出现的两种情况:非蓝即绿 Presorting 预排序很重要:否则所有的点都会满足 to-left-test BackTracks算法复杂度 …...
系统架构师2025年论文《论SOA技术的应用》
摘要: 本人于XXXX年XX月参加某市医院《预约挂号系统》的开发工作,在该项目中主要担任系统架构师,主要负责该系统架构和网络安全体系架构设计。经过多年的医院信息化建设,某市医院已经建立了一些应用系统,但是…...
React+TS编写轮播图
当前轮播图存在部分问题,一次循环结束,进入下一次需要点击两次(所以动画效果上点击第二次才出现) 轮播图:实现无限循环轮播图的关键在于"视觉欺骗"——我们在实际数据的前后各添加部分数据副本,当…...
山东大学创新项目实训开发日志(19)之前端知识深度学习
今天晚上在队长的带领下学习了一下前端vue的基础知识 reactive和ref函数 refreactive数据类型原始数据、对象对象操作js中需要添加.value,tamplate中则不用都不用添加.value computed和watch computed 写法 <script setup>const Factorial computed(() &g…...
【C++详解】C++入门(一)
文章目录 一、命名空间命名空间的基本特性命名空间的使用 二、C输入输出用法三、缺省参数(默认参数)定义用法 四、函数重载 一、命名空间 命名空间的基本特性 #include <stdio.h> #include <stdlib.h>int rand 10;int main() {// 编译报错:error C23…...
MAC-从es中抽取数据存入表中怎么实现
使用 Java 从 Elasticsearch 抽取数据并存入数据库表的完整实现方案: 1. Maven 依赖配置 <dependencies><!-- Elasticsearch --><dependency><groupId>org.elasticsearch.client</groupId><artifactId>elasticsearch-rest-high-level-c…...
Android串口通信
最近因为需要在Android平台进行电子秤的开发,首先第一步就是需要解决Android串口通信获取电子秤的称重信息。 google官方给我们提供了现成的解决方案,里面有编译好的apk文件还有源代码可以直接参考使用。地址:http://code.google.com/p/andr…...
QT常见输入类控件及其属性
Line Edit QLineEdit用来表示单行输入框,可以输入一段文本,但是不能换行 核心属性: 核心信号 信号 说明 void cursorPositionChanged(int old,int new) 当鼠标移动时发出此型号,old为先前位置,new为新位置 void …...