二叉树 ---- 所有结点数
普通二叉树的结点数:
递归法:
对二叉树进行前序or后序遍历:
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//计算普通二叉树的结点数
int nodenums(linklist node)
{if(node == nullptr) return 0; //node为空就返回0int leftnums = nodenums(node->leftChild); //左子树的数量通过递归计算出来int rightnums = nodenums(node->rightChild); //右子树的数量通过递归计算出来return leftnums + rightnums + 1;返回左子树的数量 + 右子树的数量 + 1(根结点的数量)
}
化简写法:
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//计算普通二叉树的结点数
int nodenums(linklist node)
{if(node == nullptr) return 0;return 1 + nodenums(node->leftChild) + nodenums(node->rightChild);
}
队列法:
利用BFS的思想层序遍历:
#include <queue>
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//法二(BFS)
int coutnode(linklist node)
{queue<linklist> q; //建立新的linklist型队列qif(node == nullptr) q.push(node); //如果node不为空,就把结点node推进队列int result = 0;//result用来存结点数//BFS层序遍历while(q.empty()){int size = q.size();for(int i = 0;i < size;i++){linklist p = q.front();q.pop();result++; //记录结点数if(p->leftChild) q.push(node->leftChild);if(p->rightChild) q.push(node->rightChild);}}return result;
}
完全二叉树的结点数:
完全二叉树的本身会包含满二叉树,可以简便写,先判断最大的满二叉树的位置然后再利用普通二叉树的递归遍历方法进行计算。
如果遇到满二叉树,则返回满二叉树的结点数,可以利用公式2^n-1,利用位运算(2 << n) - 1。
(n为深度),也可以利用我前面的文章讲述的快速幂利用递归求出二次幂。
int nodenum(linklist node)
{if(node == nullptr) return 0;linklist left = node->leftChild;linklist right = node->rightChild;//左右子树深度int leftdepth = 0;int rightdepth = 0;while(left){left = left->leftChild;leftdepth++;}while(right){right = right->rightChild;rightdepth++;}//如果左右子树的深度相等就是满二叉树if(leftdepth == rightdepth) return (2 << leftdepth) - 1;//满二叉树的计算结点公式2^n-1return 1 + nodenum(node->leftChild) + nodenum(node->rightChild);
}
判断平衡二叉树:
二叉树中任意结点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树 。
所以abs(左子树深度 - 右子树深度) > 1就不是平衡二叉树。
所以先按照最大深度的计算方法递归左右子树的最大深度然后判断是否符合平衡二叉树,如果不是就return返回false,最后return返回平衡二叉树的最大深度。
typedef struct Tree
{int data;Tree* leftChild;Tree* rightChild;
}tree,*linklist;
//如果不是平衡二叉树,那么就返回-1记录其不是平衡二叉树
int balancedepth(linklist node)
{int leftdepth = balancedepth(node->leftChild);if(leftdepth == -1) return -1;int rightdepth = balancedepth(node->rightChild);if(rightdepth == -1) return -1;if(abs(leftdepth - rightdepth) > 1) return -1;//不平衡return 1 + max(leftdepth , rightdepth);
}
输入一棵二叉树的根结点,判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过 1,那么它就是一棵平衡二叉树。
注意:
- 规定空树也是一棵平衡二叉树。
数据范围
树中节点数量 [0,500]。
样例
输入:二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示,5/ \7 11/ \12 9输出:true
struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:bool isBalanced(TreeNode* root) {int res = dfs(root);if(res != -1) return true;else return false;}int dfs(TreeNode* root){if(!root) return 0;int leftdepth = dfs(root->left),rightdepth = dfs(root->right);if(leftdepth == -1 || rightdepth == -1) return -1;if(abs(rightdepth - leftdepth) > 1) return -1;return 1 + max(leftdepth , rightdepth);}
};
今天内容到这里了,感谢收看。
相关文章:
二叉树 ---- 所有结点数
普通二叉树的结点数: 递归法: 对二叉树进行前序or后序遍历: typedef struct Tree {int data;Tree* leftChild;Tree* rightChild; }tree,*linklist; //计算普通二叉树的结点数 int nodenums(linklist node) {if(node nullptr) return 0; …...
步步深入 k8s 使用 pv pvc sc 在 nfs 基础上共享存储
博客原文 文章目录 前言集群环境nfs 环境搭建pod 挂载 nfs架构图 pvc 方式挂载 nfs架构图 storageclass 方式动态申请 pv架构图 参考 前言 持久化卷(Persistent Volume, PV)允许用户将外部存储映射到集群,而持久化卷申请(Persist…...
Stable Diffusion 模型下载:Disney Pixar Cartoon Type A(迪士尼皮克斯动画片A类)
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十...
Modelsim10.4安装
简介(了解,可跳过) modelsim是Mentor公司开发的优秀的HDL语言仿真软件。 它能提供友好的仿真环境,采用单内核支持VHDL和Verilog混合仿真的仿真器。它采用直接优化的编译技术、Tcl/Tk技术和单一内核仿真技术,编译仿真速…...
Java基于微信小程序的医院核酸检测服务系统,附源码
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...
VC++ 绘制折线学习
win32 有三个绘制折线的函数; Polyline,根据给定点数组绘制折线; PolylineTo,除了绘制也更新当前位置; PolyPolyline,绘制多条折线,第一个参数是点数组,第二个参数是一个数组、指…...
速盾:dns解析和cdn加速的区别与联系
DNS解析和CDN加速是两种不同的网络技术,但在网站访问过程中起到了相互协作的作用。 首先,DNS解析(Domain Name System)是将域名转换为IP地址的过程。当用户输入一个网址时,计算机会先向本地DNS服务器发送一个查询请求…...
C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统(3) 保存表格数据
对上两篇篇的工作C Qt框架开发| 基于Qt框架开发实时成绩显示排序系统(1)-CSDN博客和C Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统(2)折线图显示-CSDN博客继续优化,增加一个保存按钮,用于保存成绩数据…...
ChatGPT 4:新特性与优势
ChatGPT 4:新特性与优势 一、引言 ChatGPT 4是一款备受瞩目的人工智能模型,它以其强大的语言生成能力和智能回答能力,为用户提供了更高效、更便捷的对话体验。为了能够充分享受ChatGPT 4的各项功能,本文将向您详细介绍其新特性&…...
【教程】MySQL数据库学习笔记(二)——数据类型(持续更新)
写在前面: 如果文章对你有帮助,记得点赞关注加收藏一波,利于以后需要的时候复习,多谢支持! 【MySQL数据库学习】系列文章 第一章 《认识与环境搭建》 第二章 《数据类型》 文章目录 【MySQL数据库学习】系列文章一、整…...
Servo的并发模型介绍
Servo是一个由Mozilla Research开发的实验性浏览器引擎,旨在为未来的网页和应用程序提供高性能的渲染。Servo的并发模型是其核心特点之一,它利用现代多核处理器的优势,通过异步编程和并行处理来提高渲染效率和响应性。以下是对Servo并发模型的…...
Vue3大事件项目(ing)
文章目录 核心内容1.大事件项目介绍2.大事件项目创建3.Eslint配置代码风格4.配置代码检查工作流问题: pnpm lint是全量检查,耗时问题,历史问题 5.目录调整6.vue-router4 路由代码解析7.引入 Element Plus 组件库8.Pinia 构建仓库 和 持久化9.Pinia 仓库统一管理 核心内容 Vue3…...
基于spring boot实现邮箱发送和邮箱验证
目录 一、邮箱发送实现1. 开通邮箱服务2. 添加邮箱依赖3.添加配置4.添加邮箱通用类5. 测试类 二、邮箱验证实现1.添加依赖2. 添加配置3.添加controller4. 测试 项目地址: https://gitee.com/nssnail/springboot-email 一、邮箱发送实现 1. 开通邮箱服务 使用qq邮箱、163邮箱都…...
华清作业day56
SQLite特性: 零配置一无需安装和管理配置;储存在单一磁盘文件中的一个完整的数据库;数据库文件可以在不同字节顺序的机器间自由共享;支持数据库大小至2TB;足够小,全部源码大致3万行c代码,250KB…...
【FPGA】VHDL:八段码到8421BCD码转换电路
目录 EDA设计基础练习题 : 实验要求如下: 代码 八段码到8421BCD码转换电路 8421BCD码到八段码转换电路 八段码到8421BCD~运行结果展示 8421BCD转八段码~运行结果展示 特别注意 软件:Quartus II 13.0 (64-bit) 语言:VHDL E…...
docker安装、运行
1、安装 之前有docker的话,需要先卸载旧版本: sudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine 安装之前需要安装yum工具: sud…...
新型RedAlert勒索病毒针对VMWare ESXi服务器
前言 RedAlert勒索病毒又称为N13V勒索病毒,是一款2022年新型的勒索病毒,最早于2022年7月被首次曝光,主要针对Windows和Linux VMWare ESXi服务器进行加密攻击,到目前为止该勒索病毒黑客组织在其暗网网站上公布了一名受害者&#x…...
qt-C++笔记之判断一个QLabel上有没有load图片
qt-C笔记之判断一个QLabel上有没有load图片 code review! 在Qt框架中,QLabel是用来显示文本或者图片的一个控件。如果你想判断一个QLabel控件上是否加载了图片,你可以检查它的pixmap属性。pixmap属性会返回一个QPixmap对象,如果没有图片被加…...
鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Menu组件
鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Menu组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Menu组件 以垂直列表形式显示的菜单。 子组件 包含MenuItem、MenuItemGroup子组…...
vue三种路由守卫详解
在 Vue 中,可以通过路由守卫来实现路由鉴权。Vue 提供了三种路由守卫:全局前置守卫、全局解析守卫和组件内的守卫。 全局前置守卫 通过 router.beforeEach() 方法实现,可以在路由跳转之前进行权限判断。在这个守卫中,可以根据用…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
