222. 完全二叉树的节点个数 - 力扣(LeetCode)

题目描述

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

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

题目示例

在这里插入图片描述

输入:root = [1,2,3,4,5,6]
输出:6

解题思路

在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。
在这里插入图片描述
可以看出如果整个树不是满二叉树,就递归其左右孩子,直到遇到满二叉树为止,用公式计算这个子树(满二叉树)的节点数量。

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢?

在完全二叉树中,如果递归向左遍历的深度等于递归向右遍历的深度,那说明就是满二叉树。

在这里插入图片描述

参考代码

class Solution {public int countNodes(TreeNode root) {// 普通二叉树使用任何方式都可以计算节点个数// 但是这是完全二叉树,目的很明确,让你用完全二叉树的特性// 利用完全二叉树的特性来求节点个数// 满二叉树,最左侧深度和最右侧深度是一样的// 完全二叉树内总有一个满二叉树if(root == null) return 0;TreeNode left = root.left;TreeNode right = root.right;int leftDepth = 0;int rightDepth = 0;while(left != null) {leftDepth++;left = left.left;}while(right != null) {rightDepth++;right = right.right;}if(leftDepth == rightDepth) {return (2 << leftDepth) - 1;}int leftNum = countNodes(root.left);int rightNum = countNodes(root.right);return leftNum + rightNum + 1;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2774441.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

20240207-不要用摸鱼打发时间

20240207-不要用摸鱼打发时间 今天是农历年倒数第三天&#xff0c;很多人都已经回家过年了。我有其他出行计划&#xff0c;所以今年没有回家。其实这一点也有违背自己每年都要回家的原则&#xff0c;但相比往年&#xff0c;真的是更愿意出去不愿意回家了。 想家吗&#xff0c;…

FPGA_简单工程_无源蜂鸣器驱动实验

一 理论 蜂鸣器按其结构可分为电磁式蜂鸣器和压电式蜂鸣器2中类型&#xff0c;按其有无信号源&#xff0c;分为有源蜂鸣器和无源蜂鸣器。 有源蜂鸣器&#xff0c;内部装有集成电路&#xff0c;不需要音频驱动电路&#xff0c;就直接能发出声响&#xff0c;而无源蜂鸣器&#…

算法——前缀和算法

1. 什么是前缀和算法 前缀和算法&#xff08;Prefix Sum&#xff09;是一种用于快速计算数组元素之和的技术。它通过预先计算数组中每个位置前所有元素的累加和&#xff0c;将这些部分和存储在一个新的数组中&#xff0c;从而在需要计算某个区间的和时&#xff0c;可以通过简单…

C++ 内存管理(newdelete)

目录 本节目标 1. C/C内存分布 2. C语言中动态内存管理方式&#xff1a;malloc/calloc/realloc/free 3. C内存管理方式 3.1 new/delete操作内置类型 3.2 new和delete操作自定义类型 4. operator new与operator delete函数 5. new和delete的实现原理 6. 定位new表达式(placem…

设置idea中放缩字体大小

由于idea没默认支持ctrl滚轴对字体调节大小&#xff0c;下面一起设置一下吧&#xff01; 点击 文件 -> 设置 按键映射 -> 编辑器操作 -> 搜索栏输入f 点击减小字体大小 -> 选择增加鼠标快捷键 按着ctrl键&#xff0c;鼠标向下滚动后&#xff0c;点击确定即可 然后…

微软.NET6开发的C#特性——类、结构体和联合体

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;看到不少初学者在学习编程语言的过程中如此的痛苦&#xff0c;我决定做点什么&#xff0c;下面我就重点讲讲微软.NET6开发人员需要知道的C#特性。 C#经历了多年发展&#xff0c; 进行了多次重大创新&#xf…

Hadoop搭建(完全分布式)

节点分布&#xff1a; bigdata-masterbigdata-slave1bigdata-salve2 NameNode NodeManager NodeManager SecondaryNameNodeDataNodeDataNodeResourceManagerNodeManagerDataNode 目录 一、jdk安装&#xff1a; 二、hadoop安装 一、jdk安装&#xff1a; jdk-8u212链接&am…

git 使用 (备查)

git忽略清单 添加忽略清单 SSH免登录 ssh协议可以实现免登录操作&#xff0c;身份验证通过密钥实现。 跨团队写作 解决冲突 拉取 克隆 拉取最新版本 推送 远程仓库别名 直接使用git push推送 多人协作开发 分支命令 合并分支命令在主分支使用&#xff0c;将develop分支合并到…

【力扣】快乐数,哈希集合 + 快慢指针 + 数学

快乐数原题地址 方法一&#xff1a;哈希集合 定义函数 getNext(n) &#xff0c;返回 n 的所有位的平方和。一直执行 ngetNext(n) &#xff0c;最终只有 2 种可能&#xff1a; n 停留在 1 。无限循环且不为 1 。 证明&#xff1a;情况 1 是存在的&#xff0c;如力扣的示例一…

【C++基础入门】七、指针(定义和使用、所占内存空间、空指针和野指针、const关键字修饰指针、指针和数组、指针和函数)

七、指针 7.1 指针的基本概念 指针的作用&#xff1a; 可以通过指针间接访问内存 内存编号是从0开始记录的&#xff0c;一般用十六进制数字表示可以利用指针变量保存地址 7.2 指针变量的定义和使用 指针变量定义语法&#xff1a; 数据类型 * 变量名&#xff1b; 示例&…

深入Pandas:精通文本数据处理的20+技巧与应用实例【第68篇—python:文本数据处理】

文章目录 Pandas文本数据处理方法详解1. str/object类型转换2. 大小写转换3. 文本对齐4. 获取长度5. 出现次数6. 编码方向7. 字符串切片8. 字符串替换9. 字符串拆分10. 字符串连接11. 字符串匹配12. 去除空格13. 多条件过滤14. 字符串排序15. 字符串格式化16. 多列文本操作17. …

PHPExcel导出excel

PHPExcel下载地址 https://gitee.com/mirrors/phpexcelhttps://github.com/PHPOffice/PHPExcel 下载后目录结构 需要的文件如下图所示 将上面的PHPExcel文件夹和PHPExcel.php复制到你需要的地方 这是一个简单的示例代码 <?php$dir dirname(__FILE__); //require_once …

「Mybatis实战五」:Mybatis核心文件详解 - MyBatis常用配置environments、properties

一、MyBatis核心配置文件层级关系 ​ 本文代码在 Mybatis初体验&#xff1a;一小时从入门到运行你的第一个应用 所构建的基础代码结构之上&#xff0c;进行修改。 MyBatis 的配置文件包含了会深深影响 MyBatis 行为的设置和属性信息。 配置文档的顶层结构如下&#xff1a; 二…

Github 2024-02-08 开源项目日报 Top9

根据Github Trendings的统计&#xff0c;今日(2024-02-08统计)共有9个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Ruby项目1HTML项目1Python项目1Scala项目1PLpgSQL项目1Rust项目1NASL项目1C项目1TypeScript项目1非开发语言项目…

vue3:26—新的内置组件

目录 Teleport Suspense Teleport 什么是Teleport? Teleport 是一种能够将我们的组件html结构移动到指定位置的技术 当在元素中的css使用了filter滤镜属性的时候&#xff0c;会导致内部 fixed 元素定位发生错误&#xff0c;即不再相对 viewport 进行定位&#xff0c;而是相对…

Redis篇之redis是单线程

一、redis是单线程 Redis是单线程的&#xff0c;但是为什么还那么快&#xff1f;主要原因有下面3点原因&#xff1a; 1. Redis是纯内存操作&#xff0c;执行速度非常快。 2. 采用单线程&#xff0c;避免不必要的上下文切换可竞争条件&#xff0c;多线程还要考虑线程安全问题。 …

【Google Bard】免费生成图像——功能和使用方法详解

Google Bard 关于Bard 图片生成功能打开Bard通过Bard来生成图片Bard Vs Bing Vs Dall-EBard的生成结果Bing的生成结果Dall-E 的生成结果 总结 关于Bard 图片生成功能 Google在2月1日&#xff08;当地时间&#xff09;宣布&#xff0c;其对话型AI“Bard”新增了图像生成功能。 …

ICLR 2024 | Harvard FairSeg:第一个研究分割算法公平性的大型医疗分割数据集

近年来&#xff0c;人工智能模型的公平性问题受到了越来越多的关注&#xff0c;尤其是在医学领域&#xff0c;因为医学模型的公平性对人们的健康和生命至关重要。高质量的医学公平性数据集对促进公平学习研究非常必要。现有的医学公平性数据集都是针对分类任务的&#xff0c;而…

【Java】ArrayList和LinkedList的区别是什么

目录 1. 数据结构 2. 性能特点 3. 源码分析 4. 代码演示 5. 细节和使用场景 ArrayList 和 LinkedList 分别代表了两类不同的数据结构&#xff1a;动态数组和链表。它们都实现了 Java 的 List 接口&#xff0c;但是有着各自独特的特点和性能表现。 1. 数据结构 ArrayList…

泽攸科技ZEM系列台扫助力环境科研创新:可见光催化抗生素降解的探索

环境污染和能源短缺是当今人类社会面临的最严重威胁之一。为了克服这些问题&#xff0c;特别是在污水处理过程中&#xff0c;寻找新的技术来实现清洁、高效、经济的发展显得尤为重要。在各种工业废水中&#xff0c;抗生素的过量排放引起了广泛关注。抗生素的残留会污染土壤、水…