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

【二叉树算法题记录】222. 完全二叉树的节点个数

题目描述

给你一棵 完全二叉树 的根节点root ,求出该树的节点个数。

完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

题目分析

迭代法

简单暴力直接上层次遍历!(万能的层次遍历)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {// 层次遍历queue<TreeNode*> q;if(root!=NULL) q.push(root);int num = 0;    // 节点个数numwhile(!q.empty()){int size = q.size();while(size--){  // 遍历每层节点TreeNode* node = q.front();q.pop();num++;// 放入该节点下层的左右孩子if(node->left) q.push(node->left);if(node->right) q.push(node->right);}}return num;}
};

递归法

递归计算左右子树的结点个数,然后合并。

class Solution {
public:int countNodes(TreeNode* root) {// 递归遍历:每一层都在计算子树的节点数量// 递归终止条件:if(root==NULL) return 0;int left = countNodes(root->left);int right = countNodes(root->right);int total = left + right + 1;return total;}
};

不过这题有个特殊条件:完全二叉树。完全二叉树有两种情况,一种是满二叉树,另一种是最后一层叶子节点不是满的。我们知道,满二叉树的节点数是很好计算的,也就是 2 n − 1 2^n-1 2n1 n n n是深度。那么我们可以利用递归计算寻找到的满二叉树的节点数量,一层一层传上来,就得到了整体完全二叉树的节点数量。

class Solution {
public:int countNodes(TreeNode* root) {// 递归法// 递归终止条件if(root==NULL) return 0;TreeNode* left = root->left;TreeNode* right = root->right;int leftDepth = 0, rightDepth = 0;while(left) {left = left->left;leftDepth++;}while(right){right = right->right;rightDepth++;}if(leftDepth==rightDepth){  // 判断当前子树是不是满二叉树,即左右深度相同// 如果是满二叉树,则返回节点个数return (2 << leftDepth) - 1;}// 单层递归逻辑return countNodes(root->left) + countNodes(root->right) + 1;}
};

相关文章:

【二叉树算法题记录】222. 完全二叉树的节点个数

题目描述 给你一棵 完全二叉树 的根节点root &#xff0c;求出该树的节点个数。 完全二叉树的定义如下&#xff1a;在完全二叉树中&#xff0c;除了最底层节点可能没填满外&#xff0c;其余每层节点数都达到最大值&#xff0c;并且最下面一层的节点都集中在该层最左边的若干位…...

每日新闻掌握【2024年5月6日 星期一】

2024年5月06日 星期一 农历三月廿八 大公司/大事件 多个品牌黄金优惠后价格重回600元/克以下 “五一”假期期间&#xff0c;记者走访调研黄金消费市场发现&#xff0c;受国际金价回落及“五一”假期促销等多重因素影响&#xff0c;终端黄金价格出现了较为明显的回落。包括周大…...

谈谈Tcpserver开启多线程并发处理遇到的问题!

最近在学习最基础的socket网络编程&#xff0c;在Tcpserver开启多线程并发处理时遇到了一些问题&#xff01; 说明 在linux以及Windows的共享文件夹进行编写的&#xff0c;所以代码中有的部分使用 #ifdef WIN64 ... #else ... #endif 进入正题&#xff01;&#xff01;&…...

618好物节不知道买什么?快收下这份好物推荐指南!

随着618好物节的临近&#xff0c;你是否在为选择什么产品而犹豫不决&#xff1f;不用担忧&#xff0c;我精心准备了一份购物指南&#xff0c;旨在帮助你发现那些性价比高、口碑爆棚的商品。无论是科技新品还是生活小物件&#xff0c;这份指南都能帮你快速定位到那些值得投资的好…...

Django高级表单处理与验证实战

title: Django高级表单处理与验证实战 date: 2024/5/6 20:47:15 updated: 2024/5/6 20:47:15 categories: 后端开发 tags: Django表单验证逻辑模板渲染安全措施表单测试重定向管理最佳实践 引言&#xff1a; 在Web应用开发中&#xff0c;表单是用户与应用之间进行交互的重要…...

类和对象-Python-第一部分

初识对象 使用对象组织数据 class Student:nameNonegenderNonenationalityNonenative_placeNoneageNonestu_1Student()stu_1.name"林军杰" stu_1.gender"男" stu_1.nationality"中国" stu_1.native_place"山东" stu_1.age31print(stu…...

Pytorch实现图片异常检测

图片异常检测 异常检测指的是在正常的图片中找到异常的数据&#xff0c;由于无法通过规则进行识别判断&#xff0c;这样的应用场景通常都是需要人工进行识别&#xff0c;比如残次品的识别&#xff0c;图片异常识别模型的目标是可以代替或者辅助人工进行识别异常图片。 AnoGAN…...

【NOI-题解】1586. 扫地机器人1430 - 迷宫出口1434. 数池塘(四方向)1435. 数池塘(八方向)

文章目录 一、前言二、问题问题&#xff1a;1586 - 扫地机器人问题&#xff1a;1430 - 迷宫出口问题&#xff1a;1434. 数池塘&#xff08;四方向&#xff09;问题&#xff1a;1435. 数池塘&#xff08;八方向&#xff09; 三、感谢 一、前言 本章节主要对深搜基础题目进行讲解…...

探究MySQL行格式:解析DYNAMIC与COMPACT的异同

在MySQL中&#xff0c;行格式对于数据存储和检索起着至关重要的作用。MySQL提供了多种行格式&#xff0c;其中DYNAMIC和COMPACT是两种常见的行格式。 本文将深入探讨MySQL行格式DYNAMIC和COMPACT的区别&#xff0c;帮助读者更好地理解它们的特点和适用场景。 1. MySQL行格式简…...

MATLAB绘制蒸汽压力和温度曲线

蒸汽压力与温度之间的具体关系公式一般采用安托因方程&#xff08;Antoine Equation&#xff09;&#xff0c;用于描述纯物质的蒸汽压与温度之间的关系。安托因方程的一般形式如下&#xff1a; [\log_{10} P A - \frac{B}{C T}] 其中&#xff0c; (P) 是蒸汽压&#xff08…...

repo跟git的关系

关于repo 大都讲的太复杂了,大多是从定义角度跟命令角度去讲解,其实从现实项目使用角度而言repo很好理解. 我们都知道git是用来管理项目的,多人开发过程中git功能很好用.现在我们知道一个项目会用一个git仓库去管理,项目的开发过程中会使用git创建分支之类的来更好的维护项目代…...

Mysql 8.0 -- 最新版本安装(保姆级教程)

Mysql 8.0 -- 最新版本安装&#xff08;保姆级教程&#xff09; ​​ 一&#xff0c;下载Mysql数据库&#xff1a; 官网链接&#xff1a;https://www.mysql.com/downloads/ 二&#xff0c;安装Mysql: 三&#xff0c;找到Mysql安装目录&#xff1a; 找到mysql安装目录&#xf…...

sql优化思路

sql的优化经验 这里解释一下SQL语句的优化的原理 1.指明字段名称&#xff0c;可以尽量使用覆盖索引&#xff0c;避免回表查询&#xff0c;因此可以提高效率 2.字面意思&#xff0c;无需过多赘述。索引就是为了提高查询效率的。 3.图中两条sql直接可以使用union all 或者 uni…...

gin学习1-7

package mainimport ("github.com/gin-gonic/gin""net/http" )// 响应json还有其他响应差不多可以去学 func _string(c *gin.Context) {c.String(http.StatusOK, "lalal") } func _json(c *gin.Context) {//json响应结构体type UsetInfo struct …...

likeshop多商户单商户商城_likeshop跑腿源码_likeshop物品租赁系统开源版怎么配置小程序对接?

本人是商业用户所以能持续得到最新商业版&#xff0c;今天我说下likeshop里面怎么打包小程序&#xff0c;大家得到程序时候会发现它有admin目录 app目录 server目录 这三个目录分别是做什么呢&#xff1f; 1.admin目录 下面都是架构文件使用得是Node.js打包得&#xff0c;至于…...

(done) LSTM 详解 (包括它为什么能缓解梯度消失)

RNN 参考视频&#xff1a;https://www.bilibili.com/video/BV1e5411K7oW/?p2&spm_id_frompageDriver&vd_source7a1a0bc74158c6993c7355c5490fc600 LSTM 参考视频&#xff1a;https://www.bilibili.com/video/BV1qM4y1M7Nv?p5&vd_source7a1a0bc74158c6993c7355c5…...

springboot使用研究

map-underscore-to-camel-case: true 开启驼峰命名 GetMapping("/userInfo")public Result<Users> userInfo(RequestHeader(name "Authorization") String token,HttpServletResponse response) {Map<String, Object> map JwtUtil.parseT…...

老旧房屋用电线路故障引起的电气火灾预防对策​

摘 要&#xff1a;在我国新农村建设方针指引下&#xff0c;农村地区的发展水平有了显著提高。在农村经济发展中&#xff0c;我们也要认识到其中存在的风险隐患问题&#xff0c;其中重要的就是火灾事故。火灾事故给农村发展带来的不利影响&#xff0c;不仅严重威胁到农村群众的生…...

OpenAI发布GPT-4.0使用指南

大家好&#xff0c;ChatGPT 自诞生以来&#xff0c;凭借划时代的创新&#xff0c;被无数人一举送上生成式 AI 的神坛。在使用时&#xff0c;总是期望它能准确理解我们的意图&#xff0c;却时常发现其回答或创作并非百分之百贴合期待。这种落差可能源于我们对于模型性能的过高期…...

【WEEK11】学习目标及总结【Spring Boot】【中文版】

学习目标&#xff1a; 学习SpringBoot 学习内容&#xff1a; 参考视频教程【狂神说Java】SpringBoot最新教程IDEA版通俗易懂员工管理系统 页面国际化登录功能展示员工列表增加员工修改员工信息删除及404处理 学习时间及产出&#xff1a; 第十一周MON~SAT 2024.5.6【WEEK11】…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...