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

代码随想录阅读笔记-二叉树【总结】

二叉树的理论基础

  • 代码随想录 (programmercarl.com):二叉树的种类、存储方式、遍历方式、定义方式

二叉树的遍历方式

  • 深度优先遍历
    • 代码随想录阅读笔记-二叉树【递归遍历】-CSDN博客:递归三部曲初次亮相
    • 代码随想录阅读笔记-二叉树【迭代遍历】-CSDN博客:通过栈模拟递归
    • 代码随想录阅读笔记-二叉树【统一迭代法】-CSDN博客
  • 广度优先遍历
    • 代码随想录阅读笔记-二叉树【层序遍历】-CSDN博客:通过队列模拟

求二叉树的属性

  • 代码随想录阅读笔记-二叉树【对称二叉树】-CSDN博客
    • 递归:后序,比较的是根节点的左子树与右子树是不是相互翻转
    • 迭代:使用队列/栈将两个节点顺序放入容器中进行比较
  • 代码随想录阅读笔记-二叉树【最大深度】-CSDN博客
    • 递归:后序,求根节点最大高度就是最大深度,通过递归函数的返回值做计算树的高度
    • 迭代:层序遍历
  • 代码随想录阅读笔记-二叉树【最小深度】-CSDN博客
    • 递归:后序,求根节点最小高度就是最小深度,注意最小深度的定义
    • 迭代:层序遍历
  • 代码随想录阅读笔记-二叉树【完全二叉树节点个数】-CSDN博客
    • 递归:后序,通过递归函数的返回值计算节点数量
    • 迭代:层序遍历
  • 代码随想录阅读笔记-二叉树【平衡二叉树】-CSDN博客
    • 递归:后序,注意后序求高度和前序求深度,递归过程判断高度差
    • 迭代:效率很低,不推荐
  • 代码随想录阅读笔记-二叉树【二叉树的所有路径】-CSDN博客
    • 递归:前序,方便让父节点指向子节点,涉及回溯处理根节点到叶子的所有路径
    • 迭代:一个栈模拟递归,一个栈来存放对应的遍历路径
  • 代码随想录阅读笔记-二叉树【左叶子之和】-CSDN博客
    • 递归:后序,必须三层约束条件,才能判断是否是左叶子。
    • 迭代:直接模拟后序遍历
  • 代码随想录阅读笔记-二叉树【找树左下角的值】-CSDN博客
    • 递归:顺序无所谓,优先左孩子搜索,同时找深度最大的叶子节点。
    • 迭代:层序遍历找最后一行最左边
  • 代码随想录阅读笔记-二叉树【路径总和】-CSDN博客
    • 递归:顺序无所谓,递归函数返回值为bool类型是为了搜索一条边,没有返回值是搜索整棵树。
    • 迭代:栈里元素不仅要记录节点指针,还要记录从头结点到该节点的路径数值总和

二叉树的修改与构造

  • 代码随想录阅读笔记-二叉树【翻转二叉树】-CSDN博客
    • 递归:前序,交换左右孩子
    • 迭代:直接模拟前序遍历
  • 代码随想录-二叉树【从中序与后序遍历序列构造二叉树】-CSDN博客
    • 递归:前序,重点在于找分割点,分左右区间构造
    • 迭代:比较复杂,意义不大
  • 代码随想录阅读笔记-二叉树【最大二叉树】-CSDN博客
    • 递归:前序,分割点为数组最大值,分左右区间构造
    • 迭代:比较复杂,意义不大
  • 代码随想录阅读笔记-二叉树【合并二叉树】-CSDN博客
    • 递归:前序,同时操作两个树的节点,注意合并的规则
    • 迭代:使用队列,类似层序遍历

求二叉搜索树的属性

  • 代码随想录阅读笔记-二叉树【二叉搜索树中的搜索】-CSDN博客

    • 递归:二叉搜索树的递归是有方向的
    • 迭代:因为有方向,所以迭代法很简单
  • 代码随想录阅读笔记-二叉树【验证二叉搜索树】-CSDN博客

    • 递归:中序,相当于变成了判断一个序列是不是递增的
    • 迭代:模拟中序,逻辑相同
  • 代码随想录阅读笔记-二叉树【二叉搜索树的最小绝对差】-CSDN博客

    • 递归:中序,双指针操作
    • 迭代:模拟中序,逻辑相同
  • 代码随想录阅读笔记-二叉树【二叉搜索树中的众数】-CSDN博客

    • 递归:中序,清空结果集的技巧,遍历一遍便可求众数集合

  • 代码随想录阅读笔记-二叉树【二叉搜索树转换为累加树】-CSDN博客
    • 递归:中序,双指针操作累加

    • 迭代:模拟中序,逻辑相同

二叉树公共祖先问题

  • 代码随想录阅读笔记-二叉树【二叉树的最近公共祖先】-CSDN博客
    • 递归:后序,回溯,找到左子树出现目标值,右子树节点目标值的节点。
    • 迭代:不适合模拟回溯
  • 代码随想录阅读笔记-二叉树【二叉搜索树的最近公共祖先】-CSDN博客
    • 递归:顺序无所谓,如果节点的数值在目标区间就是最近公共祖先
    • 迭代:按序遍历

二叉搜索树的修改与构造

  • 代码随想录阅读笔记-二叉树【二叉搜索树的插入】-CSDN博客
    • 递归:顺序无所谓,通过递归函数返回值添加节点
    • 迭代:按序遍历,需要记录插入父节点,这样才能做插入操作
  • 代码随想录阅读笔记-二叉树【删除二叉搜索树节点】-CSDN博客
    • 递归:前序,想清楚删除非叶子节点的情况
    • 迭代:有序遍历,较复杂
  • 代码随想录阅读笔记-二叉树【修剪二叉搜索树】-CSDN博客
    • 递归:前序,通过递归函数返回值删除节点
    • 迭代:有序遍历,较复杂
  • 代码随想录阅读笔记-二叉树【将有序数组转换为二叉搜索树】-CSDN博客
    • 递归:前序,数组中间节点分割
    • 迭代:较复杂,通过三个队列来模拟

总结

在二叉树题目选择什么遍历顺序是不少同学头疼的事情,我们做了这么多二叉树的题目了,给大家大体分分类

  • 涉及到二叉树的构造,无论普通二叉树还是二叉搜索树一定前序,都是先构造中节点。

  • 求普通二叉树的属性,一般是后序,一般要通过递归函数的返回值做计算。

  • 求二叉搜索树的属性,一定是中序了,要不白瞎了有序性了。

注意在普通二叉树的属性中,我用的是一般为后序,例如单纯求深度就用前序,代码随想录阅读笔记-二叉树【二叉树的所有路径】-CSDN博客也用了前序,这是为了方便让父节点指向子节点。

所以求普通二叉树的属性还是要具体问题具体分析。

二叉树专题汇聚为一张图:

这个图是从 代码随想录知识星球引用,总结的非常好,分享给大家。

相关文章:

代码随想录阅读笔记-二叉树【总结】

二叉树的理论基础 代码随想录 (programmercarl.com):二叉树的种类、存储方式、遍历方式、定义方式 二叉树的遍历方式 深度优先遍历 代码随想录阅读笔记-二叉树【递归遍历】-CSDN博客:递归三部曲初次亮相代码随想录阅读笔记-二叉树【迭代遍历】-CSDN博…...

【SpringBoot整合系列】SpringBoot整合FastDFS(二)

目录 SpringBoot整合FastDFSJava客户端/依赖常用api接口解释1.uploadFile参数返回值 2.uploadSlaveFile参数返回值 3.getMetadata参数返回值 4.overwriteMetadata参数:返回值:无 5.mergeMetadata参数:返回值:无 6.queryFileInfo参…...

L2-2 巴音布鲁克永远的土(二分+并查集)

思路:我们可以二分答案,然后判断当前答案合不合理。 对于判断答案合理,可以用并查集,看mid能否把所有检查点连进一个集合中,枚举每个结点,如何当前结点周围的四个方向可以连的话,就加进同一个集…...

Spring Cloud学习笔记:Eureka简介,Eureka简单样例

这是本人学习的总结,主要学习资料如下 - 马士兵教育 [TOC](目录)1、Eureka 1.1、架构 Eureka是SpringCloud Nexflix的核心子模块,其中包含Server和Client。 Server提供服务注册,存储所有可用服务节点。 Client用于简化和Server的通讯复杂…...

【漏洞复现】WordPress Welcart 任意文件读取漏洞(CVE-2022-4140)

0x01 产品简介 Welcart 是一款免费的 WordPress 电子商务插件。Welcart 具有许多用于制作在线商店的功能和自定义设置。您可以轻松创建自己的原始在线商店。 0x02 漏洞概述 Welcart存在任意文件读取漏洞,未授权的攻击者可以通过该漏洞读取任意文件,获…...

快速排序:深入解析其原理、实现与性能特性

快速排序,以其名字所示,是一种追求速度的高效排序算法。作为分治法在排序问题上的典型应用,快速排序凭借其平均情况下近乎理想的O(n log n)时间复杂度和简洁的实现逻辑,在实际编程与数据处理中占据着重要地位。本篇博客将详细解析…...

一文看懂Mac地址

一、Mac地址是什么? 虽然IP地址已经成为一个家喻户晓的术语,但还有一个同样重要的数字标识符值得我们关注——MAC地址。在本文中,我们旨在阐明网络中这个经常被忽视的方面。加入我们,深入研究 MAC 地址的世界,了解它们…...

2024.4.10作业

#include "widget.h" #include "ui_widget.h" Widget::Widget(QWidget *parent) : QWidget(parent) , ui(new Ui::Widget) { ui->setupUi(this); } Widget::~Widget() { delete ui; } //显示时间 void Widget::timerEvent(QTimerEvent *e) { QT…...

python - Django创建项目

项目运行命令 根目录下运行命令:   python manage.py runserver win环境创建项目 直接使用 Pycharm 创建项目 在 cmd 或 Linux 命令行环境下创建 Django 项目 django-admin startproject mysite 这样就会在当前目录下创建一个叫做 mysite 的Django项目。   可以看到Djang…...

WPF —— 动画缩放变换

ScaleTransform:在二维x-y坐标系统内缩放对象; 在故事板中依赖的属性为RenderTransform.ScaleX或RenderTransform.ScaleY,这要根据你要沿哪个轴进行缩放,X代表x轴,Y代表y轴; key属性当我们使用静态资源访问时候--> <!--TargetType"{x:Type Button} 直接应用…...

SQL注入---盲注

文章目录 目录 一.盲注概述 布尔盲注&#xff1a; 时间盲注&#xff1a; 一.盲注概述 注是一种SQL注入攻击的形式&#xff0c;在这种攻击中&#xff0c;攻击者向目标应用程序发送恶意注入代码&#xff0c;然后通过观察应用程序的响应来推断出数据库中的信息。与常规的SQL注入…...

PlanUML和Mermaid哪个好?

引言 在当今信息化快速发展的时代&#xff0c;数据可视化和图表工具不仅对于程序员&#xff0c;也对于非技术背景的人士至关重要。绘图工具可以帮助我们更好地理解和表达复杂的概念或数据流。PlantUML和Mermaid是两款被广泛使用的绘图语言&#xff0c;它们都能够通过简洁的文本…...

leetcode 343. 整数拆分

题目 给定一个正整数 n &#xff0c;将其拆分为 k 个 正整数 的和&#xff08; k > 2 &#xff09;&#xff0c;并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 示例 1: 输入: n 2 输出: 1 解释: 2 1 1, 1 1 1。 示例 2: 输入: n 10 输出: 36 解释: 1…...

【MATLAB源码-第180期】基于matlab的PTS,SLM,CPFilter三种降低OFDM系统的PAPR仿真。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 1. 限幅和滤波&#xff08;Clipping and Filtering&#xff09; 原理简介 限幅和滤波是一种基础且直观的方法&#xff0c;用于降低OFDM信号的PAPR。在限幅阶段&#xff0c;信号的幅度在达到设定阈值时会被削减&#xff0c;…...

学透Spring Boot — 004. Spring Boot Starter机制和自动配置机制

如果你项目中一直用的是 Spring Boot&#xff0c;那么恭喜你没有经历过用 Spring 手动集成其它框架的痛苦。 都说 Spring Boot 大大简化了 Spring 框架开发 Web 应用的难度&#xff0c;这里我们通过配置 Hibernate 的两种方式来深刻体会这一点&#xff1a; 使用 Spring 框架集…...

面试算法-170-二叉树的最大深度

题目 给定一个二叉树 root &#xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1&#xff1a; 输入&#xff1a;root [3,9,20,null,null,15,7] 输出&#xff1a;3 解 class Solution {public int maxDepth(TreeNod…...

【数据结构】哈希

文章目录 1. 哈希概念2. 哈希冲突3. 哈希函数4. 哈希冲突解决4.1 闭散列4.2 开散列 unordered 系列的关联式容器之所以效率比较高&#xff0c;是因为其底层使用了哈希结构。 1. 哈希概念 顺序结构以及平衡树中&#xff0c;元素关键码与其存储位置之间没有对应的关系&#xff…...

Kubernetes(k8s)监控与报警(qq邮箱+钉钉):Prometheus + Grafana + Alertmanager(超详细)

Kubernetes&#xff08;k8s&#xff09;监控与报警&#xff08;qq邮箱钉钉&#xff09;&#xff1a;Prometheus Grafana Alertmanager&#xff08;超详细&#xff09; 1、部署环境2、基本概念简介2.1、Prometheus简介2.2、Grafana简介2.3、Alertmanager简介2.4、Prometheus …...

STM32-04基于HAL库(CubeMX+MDK+Proteus)中断案例(按键中断扫描)

文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式&#xff0c;生成代码四、MDK打开生成项目&#xff0c;编写HAL库的按键检测代码五、运行仿真程序&#xff0c;调试代码 一、功能需求分析 在完成GPIO输入输出案例之后&#xff0c;开始新的功能…...

第十五篇:Mybatis

文章目录 一、什么是MyBatis二、Mybatis入门案例三、配置SQL提示四、数据库连接池四、lombok五、mybatis基础操作5.1 根据id删除5.2 预编译SQL5.3 新增员工5.4 更新员工5.5 查询员工&#xff08;用于页面回显&#xff09;5.6 条件查询 七、XML映射文件八、动态SQL8.1 if语句8.2…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...