【20230210】二叉树小结
二叉树的种类
二叉树的主要形式:满二叉树和完全二叉树。
满二叉树
深度为k,有2^k-1个节点的二叉树

完全二叉树
除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。

二叉搜索树
二叉搜索树是一个有序树
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
它的左、右子树也分别为二叉排序树

平衡二叉搜索树(AVL树)
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn,注意我这里没有说unordered_map、unordered_set,unordered_map、unordered_map底层实现是哈希表。
二叉树的存储方式
二叉树可以链式存储,也可以顺序存储。
链式存储方式就是用指针,顺序存储的方式就是用数组(了解)。
顺序存储的元素在内存是连续分布的,而链式存储则是通过指针把分布在各个地址的节点串联一起。
二叉树的遍历方式
深度优先遍历:先往深处走,遇到叶子节点再往回走。
前、中、后序遍历
广度优先遍历:一层一层的遍历。
层序遍历
二叉树的定义
链式存储的二叉树节点定义:
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};二叉树的递归遍历
递归三要素:
确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件:写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
确定单层逻辑:确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
二叉树的递归遍历
递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。
前序遍历是中左右,每次先处理的是中间节点,那么先将根节点放入栈中,然后将右孩子加入栈,再加入左孩子。
迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。
先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转result数组,输出的结果顺序就是左右中了
例题:
1、从上到下打印二叉树、从上到下打印二叉树II、从上到下打印二叉树III(剑指1)
2、树的子结构、翻转二叉树、对称二叉树(剑指1)--树的子结构
关于二叉树的层序遍历:(广度优先算法)
用队列,用size记录每层的个数,每pop一个节点,判断其左右孩子是否为空,不为空就push进队列。
1.二叉树的层序遍历 、二叉树的层序遍历II、二叉树的右视图(判断当前层遍历的元素是否为最后一个元素,如果是的话就添加到数组里)
2.二叉树的层平均值(求均值的时候要做强制类型转换)
3.N叉树的层序遍历
注意N叉树节点的定义,节点的孩子是一个Node数组
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};关于二叉树的高度、深度等问题
二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
二叉树节点的高度:指从该节点到叶子节点的最长简单路径二叉树的最小深度边的条数后者节点数(取决于高度从0开始还是从1开始)
二叉树的最大深度、二叉树的最小深度
关于完全二叉树与平衡二叉树问题
完全二叉树的节点个数
后序遍历,在求完全二叉树的节点个数时,可以利用其性质,先一路向左,一路向右找最大深度,看看是否一致,相等的话,则这个节点往下为满二叉树,可以用公式2的n次方-1。
平衡二叉树
后序遍历,用返回-1的方式表达此时该节点已经不为平衡二叉树,注意这里获取高度时,如果为平衡二叉树,返回值为该节点目前的高度。与二叉树的最大深度这个题目搭配,可以很妙。
关于二叉树的路径问题
二叉树的所有路径
所有路径,肯定涉及回溯了,用中左右前序遍历。终止条件判断是否为叶子节点,中的处理要放在前面,在处理左右时要防止空指针异常。
注意这里的中处理时,将节点push进数组的操作要在终止条件之前做,因为最后一个节点也要放入数组中。
相关文章:
【20230210】二叉树小结
二叉树的种类二叉树的主要形式:满二叉树和完全二叉树。满二叉树深度为k,有2^k-1个节点的二叉树完全二叉树除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。二叉搜索树…...
openCV—图像入门(python)
目录 目标 使用OpenCV 显示图像 写入图像 总结使用 使用Matplotlib 注:图片后续补充 目标 在这里,你将了解如何使用Python编程语言中的OpenCV库,实现读取、显示和保存图像的功能。具体来说,你将学习以下函数的用法…...
关于一个Java程序员马上要笔试了,临时抱佛脚,一晚上恶补45道简单SQL题,希望笔试能通过
MySQL随手练 / DQL篇 MySQL随手练——DQL篇 题目网盘下载:https://pan.baidu.com/s/1Ky-RJRNyfvlEJldNL_yQEQ?pwdlana 初始数据 表 course 表 student 表 teacher 表 sc 答案 :) —> :( —> :) 1. 查询 "01"课程比"02"课程成绩高的学生…...
PyTorch深度学习实战
本专栏分为两大部分,专栏内容如下: 第1部分 探讨PyTorch与其他深度学习框架的区别。 如何在PyTorch Hub中下载和运行模型。 PyTorch的基本构建组件——张量 展示不同类型的数据如何被表示为张量,以及深度学习模型期望构造什么样的张量。 梯度…...
leetcode 1011. Capacity To Ship Packages Within D Days(D天内运送包裹的容量)
数组的每个元素代表每个货物的重量,注意这个货物是有先后顺序的,先来的要先运输,所以不能改变这些元素的顺序。 要days天内把这些货物全部运输出去,问所需船的最小载重量。 思路: 数组内数字顺序不能变,就…...
支持向量机SVM详细原理,Libsvm工具箱详解,svm参数说明,svm应用实例,神经网络1000案例之15
目录 支持向量机SVM的详细原理 SVM的定义 SVM理论 Libsvm工具箱详解 简介 参数说明 易错及常见问题 SVM应用实例,基于SVM的股票价格预测 支持向量机SVM的详细原理 SVM的定义 支持向量机(support vector machines, SVM)是一种二分类模型&a…...
Mac 上搭建 iOS WebDriverAgent 环境
文章目录Mac环境搭建配置 Xcode 生成 WDA常见问题brew 安装失败Mac环境搭建 macOS 系统电脑:12.6.2 Xcode:14.0.1(xcodebuild -version) appium Desktop:1.21.0 (下载链接) Appium Desktop 1.22.0 ,从该版…...
python学习笔记之例题篇NO.3
获得用户输入的一个整数N,输出N中所出现不同数字的和。 s list(set(list(input())))# ① r…...
【Kubernetes】第七篇 - Service 服务介绍和使用
一,前言 上一篇,通过配置一个 Deployment 对象,在内部创建副本集对象,副本集帮我们创建了 3 个 pod 副本 由于 pod 存在 IP 漂移现象,pod 的创建和重启会导致 IP 变化; 本篇,介绍 Service 服…...
Linux 终端复用器Tmux
目录 Tmux讲解 配置tmux 配置tmux会话 配置tmux窗口(在会话界面进行配置) 配置tmux面板 配置窗口共享同步 Tmux讲解 RHEL5/6/7使用的是screen软件包 RHEL8使用的是tumx软件包(功能更强大,更易用) tmux的三个基本…...
Hadoop集群模式安装(Cluster mode)
1、Hadoop源码编译 安装包、源码包下载地址 Index of /dist/hadoop/common/hadoop-3.3.0为什么要重新编译Hadoop源码? 匹配不同操作系统本地库环境,Hadoop某些操作比如压缩、IO需要调用系统本地库(*.so|*.dll) 修改源码、重构源码 如何…...
PTA L1-054 福到了(详解)
前言:内容包括:题目,代码实现,大致思路,代码解读 题目: “福”字倒着贴,寓意“福到”。不论到底算不算民俗,本题且请你编写程序,把各种汉字倒过来输出。这里要处理的每…...
python -- 魔术方法
魔术方法就算定义在类里面的一些特殊的方法 特点:这些func的名字前面都有两个下划线 __new__方法 相当于一个类的创建一个对象的过程 __init__方法 相当于为这个类创建好的对象分配地址初始化的过程 __del__方法 一个类声明这个方法后,创建的对象如果…...
「JVM 编译优化」提前编译器
1996 年 JDK 1.0 发布,同年 7 月 外挂即时编译器发布(JDK 1.0.2),而 Java 提前编译发布在之后几个月(IBM High Performance Compiler for Java),1998 年 GNU 组织公布 GCC 家族新成员 GNU Compi…...
Golang channel 用法与实现原理
文章目录1.简介2.用法3.三种状态4.实现原理数据结构原理概述5.小结参考文献1.简介 Golang channel 是一种并发原语,用于在不同 goroutine 之间进行通信和同步。本质上,channel 是一种类型安全的 FIFO 队列,它可以实现多个 goroutine 之间的同…...
jackson 序列化、反序列化的时候第一个大写单词变成小写了(属性设置不成功)
参考链接:https://www.baeldung.com/jackson-annotations 遇到的问题 之前和第三方对接,返回的接口中的属性名称是拼音字母大写,奇怪,反序列化的时候好多字段都为空,没设置进去。 因为对接前,我先用 IntelliJ IDEA …...
如何判断机器学习数据集是否是线性的
首先,线性和非线性函数之间的区别: 左边是线性函数,右边是非线性函数。 线性函数:可以简单定义为始终遵循以下原则的函数: 输入/输出=常数。 线性方程总是1次多项式(例如x+2y+3=0)。在二维情况下,它们总是形成直线;在其他维度中,它们也可以形成平面、点或超平面。它们的…...
后端基础SQL
SQL基础语法: sql对大小写不敏感,eg: SELECT 等效于 select;select: select用于从表中查找数据,select 列名 from 表名 —> 结果集::仅有查询列的结果表; SELECT * FROM 表名称 ----> 结果集: 查找表的所有数据…...
Ubuntu 18.04 上编译和安装内核(内核源码版本)
Ubuntu 18.04 上编译和安装内核(内核源码版本) linux发行版本为,ubuntu18.04。内核版本为5.15.7。其他版本类似。 1.下载内核源代码。可以从官方网站下载最新的内核源代码,也可以使用 Git 命令从 Linux 内核的 Git 仓库中获取最新…...
day 53|● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和 动态规划
1143. 最长公共子序列 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
