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

二叉树 ---- 所有结点数

普通二叉树的结点数:

递归法:

对二叉树进行前序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);}
};

今天内容到这里了,感谢收看。

相关文章:

二叉树 ---- 所有结点数

普通二叉树的结点数&#xff1a; 递归法&#xff1a; 对二叉树进行前序or后序遍历&#xff1a; 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架构图 参考 前言 持久化卷&#xff08;Persistent Volume, PV&#xff09;允许用户将外部存储映射到集群&#xff0c;而持久化卷申请&#xff08;Persist…...

Stable Diffusion 模型下载:Disney Pixar Cartoon Type A(迪士尼皮克斯动画片A类)

本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十...

Modelsim10.4安装

简介&#xff08;了解&#xff0c;可跳过&#xff09; modelsim是Mentor公司开发的优秀的HDL语言仿真软件。 它能提供友好的仿真环境&#xff0c;采用单内核支持VHDL和Verilog混合仿真的仿真器。它采用直接优化的编译技术、Tcl/Tk技术和单一内核仿真技术&#xff0c;编译仿真速…...

Java基于微信小程序的医院核酸检测服务系统,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

VC++ 绘制折线学习

win32 有三个绘制折线的函数&#xff1b; Polyline&#xff0c;根据给定点数组绘制折线&#xff1b; PolylineTo&#xff0c;除了绘制也更新当前位置&#xff1b; PolyPolyline&#xff0c;绘制多条折线&#xff0c;第一个参数是点数组&#xff0c;第二个参数是一个数组、指…...

速盾:dns解析和cdn加速的区别与联系

DNS解析和CDN加速是两种不同的网络技术&#xff0c;但在网站访问过程中起到了相互协作的作用。 首先&#xff0c;DNS解析&#xff08;Domain Name System&#xff09;是将域名转换为IP地址的过程。当用户输入一个网址时&#xff0c;计算机会先向本地DNS服务器发送一个查询请求…...

C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统(3) 保存表格数据

对上两篇篇的工作C Qt框架开发| 基于Qt框架开发实时成绩显示排序系统&#xff08;1&#xff09;-CSDN博客和C Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统&#xff08;2&#xff09;折线图显示-CSDN博客继续优化&#xff0c;增加一个保存按钮&#xff0c;用于保存成绩数据…...

ChatGPT 4:新特性与优势

ChatGPT 4&#xff1a;新特性与优势 一、引言 ChatGPT 4是一款备受瞩目的人工智能模型&#xff0c;它以其强大的语言生成能力和智能回答能力&#xff0c;为用户提供了更高效、更便捷的对话体验。为了能够充分享受ChatGPT 4的各项功能&#xff0c;本文将向您详细介绍其新特性&…...

【教程】MySQL数据库学习笔记(二)——数据类型(持续更新)

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【MySQL数据库学习】系列文章 第一章 《认识与环境搭建》 第二章 《数据类型》 文章目录 【MySQL数据库学习】系列文章一、整…...

Servo的并发模型介绍

Servo是一个由Mozilla Research开发的实验性浏览器引擎&#xff0c;旨在为未来的网页和应用程序提供高性能的渲染。Servo的并发模型是其核心特点之一&#xff0c;它利用现代多核处理器的优势&#xff0c;通过异步编程和并行处理来提高渲染效率和响应性。以下是对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特性&#xff1a; 零配置一无需安装和管理配置&#xff1b;储存在单一磁盘文件中的一个完整的数据库&#xff1b;数据库文件可以在不同字节顺序的机器间自由共享&#xff1b;支持数据库大小至2TB&#xff1b;足够小&#xff0c;全部源码大致3万行c代码&#xff0c;250KB…...

【FPGA】VHDL:八段码到8421BCD码转换电路

目录 EDA设计基础练习题 &#xff1a; 实验要求如下&#xff1a; 代码 八段码到8421BCD码转换电路 8421BCD码到八段码转换电路 八段码到8421BCD~运行结果展示 8421BCD转八段码~运行结果展示 特别注意 软件&#xff1a;Quartus II 13.0 (64-bit) 语言&#xff1a;VHDL E…...

docker安装、运行

1、安装 之前有docker的话&#xff0c;需要先卸载旧版本&#xff1a; sudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine 安装之前需要安装yum工具&#xff1a; sud…...

新型RedAlert勒索病毒针对VMWare ESXi服务器

前言 RedAlert勒索病毒又称为N13V勒索病毒&#xff0c;是一款2022年新型的勒索病毒&#xff0c;最早于2022年7月被首次曝光&#xff0c;主要针对Windows和Linux VMWare ESXi服务器进行加密攻击&#xff0c;到目前为止该勒索病毒黑客组织在其暗网网站上公布了一名受害者&#x…...

qt-C++笔记之判断一个QLabel上有没有load图片

qt-C笔记之判断一个QLabel上有没有load图片 code review! 在Qt框架中&#xff0c;QLabel是用来显示文本或者图片的一个控件。如果你想判断一个QLabel控件上是否加载了图片&#xff0c;你可以检查它的pixmap属性。pixmap属性会返回一个QPixmap对象&#xff0c;如果没有图片被加…...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Menu组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之Menu组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Menu组件 以垂直列表形式显示的菜单。 子组件 包含MenuItem、MenuItemGroup子组…...

vue三种路由守卫详解

在 Vue 中&#xff0c;可以通过路由守卫来实现路由鉴权。Vue 提供了三种路由守卫&#xff1a;全局前置守卫、全局解析守卫和组件内的守卫。 全局前置守卫 通过 router.beforeEach() 方法实现&#xff0c;可以在路由跳转之前进行权限判断。在这个守卫中&#xff0c;可以根据用…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

华为云Flexus+DeepSeek征文 | 基于Dify构建具备联网搜索能力的知识库问答助手

华为云FlexusDeepSeek征文 | 基于Dify构建具备联网搜索能力的知识库问答助手 一、构建知识库问答助手引言二、构建知识库问答助手环境2.1 基于FlexusX实例的Dify平台2.2 基于MaaS的模型API商用服务 三、构建知识库问答助手实战3.1 配置Dify环境3.2 创建知识库问答助手3.3 使用知…...

机器学习复习3--模型评估

误差与过拟合 我们将学习器对样本的实际预测结果与样本的真实值之间的差异称为&#xff1a;误差&#xff08;error&#xff09;。 误差定义&#xff1a; ①在训练集上的误差称为训练误差&#xff08;training error&#xff09;或经验误差&#xff08;empirical error&#x…...

联邦学习带宽资源分配

带宽资源分配是指在网络中如何合理分配有限的带宽资源&#xff0c;以满足各个通信任务和用户的需求&#xff0c;尤其是在多用户共享带宽的情况下&#xff0c;如何确保各个设备或用户的通信需求得到高效且公平的满足。带宽是网络中的一个重要资源&#xff0c;通常指的是单位时间…...

使用python进行图像处理—图像变换(6)

图像变换是指改变图像的几何形状或空间位置的操作。常见的几何变换包括平移、旋转、缩放、剪切&#xff08;shear&#xff09;以及更复杂的仿射变换和透视变换。这些变换在图像配准、图像校正、创建特效等场景中非常有用。 6.1仿射变换(Affine Transformation) 仿射变换是一种…...