二叉树 ---- 所有结点数
普通二叉树的结点数:
递归法:
对二叉树进行前序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() 方法实现,可以在路由跳转之前进行权限判断。在这个守卫中,可以根据用…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
