二叉树理论基础
二叉树种类
满二叉树:每个非叶子节点都有且只有两个子节点。
和完全二叉树:除了最底层外,其他各层都是满的;最底层的节点都集中在左侧。
二叉搜索树:对于任意节点 u
,左子树上所有节
点的值都小于 u.val
,右子树上所有节点的值都大于 u.val
。
平衡二叉树:任意节点的左右子树高度差 ≤ 1。
二叉树的存储方式
「二叉树可以链式存储,也可以顺序存储。」
那么链式存储方式就用指针, 顺序存储的方式就是用数组。
遍历算法
-
深度优先遍历(DFS)
-
前序(Pre‑Order):根 → 左 → 右
/*** 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 {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();preorder(root, res);return res;}void preorder(TreeNode root,List<Integer> list){if(root == null){return;}list.add(root.val);preorder(root.left,list); preorder(root.right,list);} }
-
中序(In‑Order):左 → 根 → 右
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();inorder(root, res);return res;}void inorder(TreeNode root,List<Integer> list){if(root == null){return;}inorder(root.left,list);list.add(root.val);inorder(root.right,list);} }
-
后序(Post‑Order):左 → 右 → 根
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new LinkedList<>();inorder(root, res);return res;}void inorder(TreeNode root,List<Integer> list){if(root == null){return;} inorder(root.left,list); inorder(root.right,list);list.add(root.val);} }
-
-
广度优先遍历(BFS)/层序(Level‑Order)
-
按层自上而下、同层从左到右依次访问,通常用队列实现。
-
二叉树的定义
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;}
}
递归写法
-
确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
-
确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
-
确定单层递归的逻辑: 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
以前序遍历为例:
1.首先,确认参数,因为我们访问的是节点,所以参数要包含节点对象,其次要返回访问的数值,所以也要包含一个list对象保存访问的值
2.每一层递归的终止条件就是遇见空节点,所以判断当前节点是否为空,为空就返回
3. 前序遍历是中左右的顺序,所以在单层递归的逻辑,是要先取中节点的数值,代码如下:
迭代解决遍历
前序:因为迭代使用栈,而出栈顺序是先进后出,所以我们在遍历的时候要改变遍历的顺序,先遍历右节点,在遍历左节点,这时候就是左节点先出,符合根左右的习惯
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null){return list;}Stack<TreeNode> s = new Stack<>();s.push(root);while(!s.isEmpty()){TreeNode node = s.pop();list.add(node.val);if(node.right != null){s.push(node.right);}if(node.left != null){s.push(node.left);}}return list;
}}
中序:在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。
// 中序遍历顺序: 左-中-右 入栈顺序: 左-右
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()){if (cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();result.add(cur.val);cur = cur.right;}}return result;}
}
后序:// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}Collections.reverse(result);return result;}
}
层次遍历
思路:需要借助一个辅助队列来完成统计,即一层一层的入队
相关文章:
二叉树理论基础
二叉树种类 满二叉树:每个非叶子节点都有且只有两个子节点。 和完全二叉树:除了最底层外,其他各层都是满的;最底层的节点都集中在左侧。 二叉搜索树:对于任意节点 u,左子树上所有节 点的值都小于 u.val…...
yarn的三个资源调度策略
### YARN 的三种资源调度策略及其工作原理与区别 #### 1. **FIFO Scheduler (先进先出调度器)** FIFO Scheduler 是一种最简单的调度方式,所有的应用程序都按顺序排队等待执行。其基本逻辑如下: - 应用程序按照提交的时间先后顺序依次进入队列。 - 当集…...
leetcode0112. 路径总和-easy
1 题目:路径总和 官方标定难度:易 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ࿱…...
铁氧体和纳米晶:车载定制电感的材料选择
最近有个做车载产品的粉丝问到:我们的定制电感产品既会用到铁氧体磁芯,也会用到纳米晶磁芯,那么这两种材料,该如何选择呢? 要回答这个问题,我们首先要对两种材料做一个基本的对比。 铁氧体材料成本低&…...
MCP认证难题破解
一、MCP 认证体系现状与核心挑战 微软认证专家(MCP)体系在 2020 年后逐步向基于角色的认证转型,例如 Azure 管理员(AZ-104)、数据分析师(DP-100)等,传统 MCP 考试已被取代。当前备考的核心难题集中在以下方面: 1. 技术栈快速迭代 云原生技术占比提升:Azure 认证中,…...
ROS机器人一般用哪些传感器?
以下是ROS机器人常用传感器的分层详解及思维导图总结,涵盖传感器分类、核心参数、ROS支持及典型应用: 一、环境感知传感器 1. 视觉传感器 类型 原理 ROS支持 数据类型 典型型号/驱动 优缺点及应用场景 单目摄像头 单镜头成像,通过透视变换获取2D图像,依赖算法推断深度 驱…...
【ubuntu】在Linux Yocto的基础上去适配Ubuntu的wifi模块
一、修改wifi的节点名 1.找到wifi模块的PID和VID ifconfig查看wifi模块网络节点的名字,发现是wlx44876393bb3a(wlxmac地址) 通过udevadm info -a /sys/class/net/wlx44876393bba路径的命令去查看wlx44876393bba的总线号,端口号…...
基于WebRTC技术的EasyRTC:支持任意平台设备的实时音视频通信解决方案
一、技术架构与核心优势 EasyRTC是一套基于WebRTC技术的实时音视频通信框架,旨在为开发者提供高效、稳定、跨平台的通信解决方案。其核心优势在于支持任意平台设备,包括Web端、移动端、桌面端和嵌入式设备,真正实现“一次开发,多…...
51单片机实验四:键盘检测原理及应用实现
目录 一、实验环境与实验器材 二、实验内容及实验步骤 1.独立键盘检测 2.独立键盘(简易版本) 3.矩阵键盘检测 4.矩阵键盘(简单版,单数码管): 一、实验环境与实验器材 环境:Keli,…...
GN ninja 工程化构建例程
文章目录 1. 前言✨2. 工程实例🚩2.1 工程目录结构2.2 工程顶层.gn文件2.3 工具链配置.gn文件2.4 编译配置.gn文件2.5 编译目标配置.gn文件2.6 工程接口文件2.7 动态库编译.gn文件2.8 动态库源文件2.9 静态库编译.gn文件2.10 静态库源文件2.11 主程序编译.gn文件2.12 主程序源…...
STC定时器频率占空比程序
// // 一、宏定义区 // #include <STC15.H> //头文件 #include <intrins.h> //库函数文件 #define FOSC 12000000L //IRC频率 typedef …...
观察者 ➜ 事件总线:一路走来的碎碎念
写给未来的自己:每次手敲事件模型都要 Google,干脆把思路和踩坑一次性记清楚。文章很长,都是唠叨,目的是让自己看两眼就能把设计理由找回来。 目录 为什么我要折腾事件模型?V0 ─ 单一事件的观察者模式V1 ─ 多事件同步总线(类型拆分)V2 ─ 订阅者优先级(链式调用可控)…...
AOP基本概念
上述语句解释感觉太过玄妙不似常人能够听懂,所以结合自己理解,给自己留点备注: 首先 目标对象: 就是这要对哪个对象进行代理,因为AOP是面向切面编程,在OOP的基础上再次解耦合,这个过程需要提…...
不确定与非单调推理的概率方法
前文我们学习了“不确定与非单调推理的基本概念”,了解了不确定性推理是人工智能领域中处理不完整、不精确或模糊信息的推理方法,其核心是在前提条件或推理规则存在不确定性时,通过某种数学或逻辑机制推导出合理结论,并对结论的可靠性进行量化。不确定与非单调推理的基本概…...
device_fingerprint、device_id、hmac生成
文章目录 1. 写在前面2. 设备信息3. 数美指纹 【🏠作者主页】:吴秋霖 【💼作者介绍】:擅长爬虫与JS加密逆向分析!Python领域优质创作者、CSDN博客专家、阿里云博客专家、华为云享专家。一路走来长期坚守并致力于Python…...
centos下openjdk报:getVersion(FontConfiguration.java)异常,安装fontconfig无效问题的处理
TOC centos下openjdk报:getVersion(FontConfiguration.java)异常,安装fontconfig无效问题的处理 官网jdk包:Releases dragonwell-project/dragonwell8 背景: 为了适应国产化,使用东方通和国产jdk,从tomcat改为tongweb&#x…...
Banana Pi BPI-RV2 RISC-V 路由器开发板发售, 全球首款RISC-V路由器
Banana Pi BPI-RV2 开源路由器是矽昌通信和⾹蕉派开源社区(Banana Pi )合作设计, 联合打造全球首款RISC-V架构路由器开发板。 这是香蕉派开源社区与矽昌通信继BPI-Wifi5 低成本Wifi5 路由器合作之后的又一力作,为全球开发者与商业客户提供基于…...
自学新标日第十九课复习版本
第十九课 基本–》否定 うー>わ 单词 单词假名声调词义品物しなもの0物品,商品お皿おさら0盘子ごみごみ2垃圾初心者しょしんしゃ2初学者上級者じょうきゅうしゃ3熟练者高級こうきゅう0高级上級クラス5高级版英会話えいかいわ3英语会话コース1路线&a…...
网安加·百家讲坛 | 刘志诚:AI安全风险与未来展望
作者简介:刘志诚,乐信集团信息安全中心总监、OWASP广东区域负责人、网安加社区特聘专家。专注于企业数字化过程中网络空间安全风险治理,对大数据、人工智能、区块链等新技术在金融风险治理领域的应用,以及新技术带来的技术风险治理…...
2025年03月中国电子学会青少年软件编程(Python)等级考试试卷(二级)真题
青少年软件编程(Python)等级考试试卷(二级) 分数:100 题数:37 答案解析:https://blog.csdn.net/qq_33897084/article/details/147340870 一、单选题(共25题,共50分) 1. 老师要求大…...
@JsonView + 单一 DTO:如何实现多场景 JSON 字段动态渲染
JsonView 单一 DTO:如何实现多场景 JSON 字段动态渲染 JsonView 单一 DTO:如何实现多场景 JSON 字段动态渲染1、JsonView 注解产生的背景2、为了满足不同场景下返回对应的属性的做法有哪些?2.1 最快速的实现则是针对不同场景新建不同的 DTO…...
《深入探秘JavaScript原型链与继承机制:解锁前端编程的核心密码》
在JavaScript的奇妙世界里,原型链与继承机制犹如隐藏的宝藏,掌握它们,就如同拿到了开启高效编程大门的钥匙。对于前端开发者来说,这不仅是写出简洁、可维护代码的关键,更是深入理解JavaScript面向对象编程的基石。今天…...
Cursor 生成java测试用例
1. 安装cursor 站点:https://www.cursor.com/cn 安装后登录 2. 使用cursor 2.1 安装扩展: 组合键 CtrlShiftX,进入扩展程序页面,安装如下: Chinese:中文支持, 安装后 CtrlShiftP࿰…...
常见免杀框架的使用(3款)---【AniYaGUI1.2.0、AV_Evasion_Tool掩日、FoxBypass_V1.0】
一、AniYaGUI1.2.0免杀框架 环境:虚拟机Win10 、云服务器 工具:Xshell、CobaltStrike 项目下载地址: https://github.com/piiperxyz/AniYa 1. 安装Go语言环境 确保Win10虚拟机安装 Golang 且环境变量中包含 go 否则⽆法编译(注…...
PHP腾讯云人脸核身生成 SDK 接口调用步骤使用签名
参考腾讯云官方文档: 人脸核身 生成 SDK 接口调用步骤使用签名_腾讯云 前提条件:成功获取NonceTicket。 获取参考文档: PHP腾讯云人脸核身获取NONCE ticket-CSDN博客 function getTxFaceSign(){$appId ;$userId ;$version 1.0.0;$tic…...
LINUX418 加载YUM源 wireshark ping程序 解析
未找到挂载点 未连接 怪不得找不到 计划重启 sr0文件有了 挂载 删除 新建、修改配置文件 清空yum缓存 创建yum缓存 1.检查相关设置:虚拟机两个打钩 2.df -h查看光盘文件 3.挂载在/mnt mount -o ro /dev/sr0 /mnt 4.删除/etc/yum.repos.d 下的文件 5.新建local…...
解决Windows安全中心显示空白页面
1、电脑重装系统后,发现原本一些软件打不开了,电脑莫名认为有病毒,自动删除插件。附图。 2、第一反应是电脑防火墙的原因,默认威胁防护识别到了病毒软件,自动删除。在开始屏幕搜Windows安全中心,打开之后发…...
2.1 SQL server的安装以及一个数据表的创建
Microsoft SQL Server 2014 Express 是一个免费的、功能强大的可靠数据管理系统,为轻型网站和桌面应用程序提供丰富可靠的数据存储. 1. 下载软件并安装 https://www.microsoft.com/zh-cn/download/details.aspx?id42299 勾选SQLEXPRADV_X64_CHS.exe就够了。 可以更…...
楼梯上下检测数据集VOC+YOLO格式5462张2类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):5462 标注数量(xml文件个数):5462 标注数量(txt文件个数):5462 …...
Excel提取图片并自动上传到文件服务器(OOS),获取文件链接
Excel提取图片并自动上传到接口 在实际项目中,我们可能经常会遇到需要批量从Excel文件(.xlsx)中提取图片并上传到特定接口的场景。今天,我就详细介绍一下如何使用Python实现这一功能,本文会手把手教你搭建一个完整的解…...
python有序列表
您的代码整体结构良好,但存在一些关键错误和优化点。以下是对代码的详细评价及改进建议:---### 主要问题1. **add方法中的链表断裂问题**- **问题描述**:当向链表中间插入节点时,未正确设置新节点的next,导致后续节点丢…...
Python(23)Python异常处理完全指南:从防御到调试的工程实践
目录 一、异常处理的核心价值与行业现状二、Python异常体系深度解析2.1 内置异常分类树2.2 七大高频异常处理方案2.2.1 文件操作异常链2.2.2 类型校验防御策略 三、企业级异常处理架构3.1 分布式系统异常封装3.2 上下文管理器资源保护 四、五大核心处理原则1. 精准捕获原则2.…...
LangChain4j-第一篇 |几分钟完成deepseek 在线集成
引言:AI 集成的Hello world 在AI迅猛增长的势头下,作为Java 程序员,也想学习开发AI 的应用产品。好在Java AI 生态也在逐步的完善,我们也可以使用java 语言开发属于自己的应用产品。LangChain4j通过声明式编程模型,将…...
C语言==》字符串断行
示例代码 #include <stdio.h>int main(void) {printf("Heres one way to print a ");printf("long string.\n");printf("Heres another way to print a \ long string.\n");printf("Heres the newest way to print a ""lo…...
springboot全局异常捕获处理
一、需求 实际项目中,经常抛出各种异常,不能直接抛出异常给前端,这样用户体验相当不好,用户看不懂你的Exception,对于一些sql异常,直接抛到页面上也不安全。所以有没有好的办法解决这些问题呢,当然有了&am…...
使用Jasypt对配置文件内容加密
使用Jasypt 配置文件内容加密 一、背景 在软件开发过程中,配置文件扮演着至关重要的角色,它存储着应用程序运行所需的各种参数和设置,例如数据库连接信息、API 密钥、第三方服务的认证信息等。然而,这些配置文件中的信息往往包含…...
opencv函数展示3
一、图像平滑(模糊) 线性滤波(速度快): 1.cv2.blur() 2.cv2.boxFilter() 3.cv2.GaussianBlur() 非线性滤波(速度慢但效果好): 4.cv2.medianBlur() 5.cv2.bilateralFilter() 二、锐…...
linux 4.14内核jffs2文件系统不自动释放空间的bug
前段时间在做spi-nor flash项目的时候,使用jffs2文件系统,发现在4.14内核下存在无法释放空间的bug,后来进行了修复,修复后功能正常,现将修复patch公开,供后来者学习: diff --git a/fs/jffs2/ac…...
华为仓颉智能体开发框架 Cangjie Magic深度解析
华为仓颉智能体开发框架 Cangjie Magic 深度解析 华为仓颉社区推出的 Cangjie Magic 是全球首个基于自研仓颉编程语言原生构建的 LLM Agent(大语言模型智能体) 开发框架,通过三大核心技术突破重构了智能体开发范式,为全场景智能化应用开发提供了全新工具链。以下从核心技术…...
Harmony5.0 设置应用全屏模式,隐藏导航栏和状态栏
Harmony5.0 设置应用全屏模式,隐藏导航栏和状态栏 在应用入口EntryAbility里添加 完整代码如下: import { AbilityConstant, ConfigurationConstant, UIAbility, Want } from @kit.AbilityKit; import { hilog } from @kit.PerformanceAnalysisKit; import { window } fro…...
6. 实战(二):用Spring AI+OpenAI构建企业级智能客服
1、引言 前面几篇已经加深了我们对Spring Ai的体系结构,核心概念,以及也有初步集成实现了一个简单demo。今天,我们通过使用Spring AI框架与OpenAI API集成,构建一个功能完善的智能对话系统,加深我们对Spring AI从概念…...
线上健身预约小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的一款线上健身预约小程序源码,其主要功能包括搜索教练、课程、门店,以及轻松预约健身项目。 用户只需通过指尖轻点,即可快速查找并预约心仪的健身课程,无需繁琐的线下操作步骤。此外,…...
掌握MySQL:基本查询指令与技巧
🍑个人主页:Jupiter. 🚀 所属专栏:MySQL初阶学习笔记 欢迎大家点赞收藏评论😊 目录 表的增删查改1 CreateInsert1.1 单行数据 全列插入指定列插入1.2 多行数据插入 指定列插入1.3 插入否则更新 1.4 替换 2 Retrieve …...
本地生活服务信息分类信息系统
最近在找分类信息系统,看了很多市面上常见的分类信息系统: 1,私集分类信息系统 2,火鸟分类信息系统 3,觅分类信息系统 4,框分类信息系统 5,蚂蚁分类信息系统 发现很多分类信息系统,…...
视频编解码种类/技术/区别/优缺点汇总
视频编解码种类/技术/区别/优缺点汇总 按国家/机构划分的全球主要视频编码标准 (含优缺点)视频编解码涉及到的主要技术及通俗解释主流视频编码标准的实现方式 按国家/机构划分的全球主要视频编码标准 (含优缺点) 组织/国家分类标准名称 (常用名/别名)推出年份 (约)主要制定组织…...
【专题刷题】双指针(四):最接近的三数之和,接雨水
📝前言说明: 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录,按专题划分每题主要记录:(1)本人解法 本人屎山代码;(2)优质解法 优质代码;ÿ…...
星露谷物语 7000+ 大型MOD整合包
衣服美化、家具美化、地图美化、人物肖像美化 全地图装修存档、人物美化、扩展包、环境美化、家具、动植物、通用前置包、新增NPC、功能、服装发饰妆 帽子发型农场小镇美化大型玩法拓展实用功能mod 动漫人物形象MOD 地点/动物/地图/功能/机械/家具/建筑/界面美化/扩展/农场/食谱…...
Vue自定义指令-防抖节流
Vue2版本 // 防抖 // <el-button v-debounce"[reset,click,300]" ></el-button> // <el-button v-debounce"[reset]" ></el-button> Vue.directive(debounce, { inserted: function (el, binding) { let [fn, event "cl…...
几款开源C#插件框架
有几个优秀的开源C#插件框架可供选择,它们提供了更完善的功能和更好的扩展性。以下是几个主流的开源C#插件框架: 1. MEF (Managed Extensibility Framework) 官方库:System.ComponentModel.Composition 特点: .NET官方提供的插件系统 基于特性(Attribute)的声明式组件注册…...
PHP使用pandoc把markdown文件转为word
文章目录 首先安装pandocPHP处理 服务器操作系统是Linux,centos 首先安装pandoc yum install -y pandoc安装完成后输入如下代码,检查安装是否成功 pandoc --versionPHP处理 我把markdown内容存到了数据库里,所以要从数据库读取内容。对内容…...