当前位置: 首页 > 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】…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...