坚持刷题 | 完全二叉树的节点个数
Hello,大家好,我是阿月!坚持刷题,老年痴呆追不上我,今天刷:完全二叉树的节点个数
题目
222.完全二叉树的节点个数

代码实现
class TreeNode {int val;TreeNode left, right;public TreeNode(int val) {this.val = val;this.left = this.right = null;}
}public class CompleteBinaryTreeCount {// 计算完全二叉树的节点个数public int countNodes(TreeNode root) {if (root == null) {return 0;}int leftHeight = leftHeight(root);int rightHeight = rightHeight(root);if (leftHeight == rightHeight) {// 左子树是满二叉树return (1 << leftHeight) - 1;} else {// 左子树不是满二叉树,递归计算左右子树的节点数return 1 + countNodes(root.left) + countNodes(root.right);}}// 计算左子树的高度private int leftHeight(TreeNode root) {int height = 0;while (root != null) {height++;root = root.left;}return height;}// 计算右子树的高度private int rightHeight(TreeNode root) {int height = 0;while (root != null) {height++;root = root.right;}return height;}public static void main(String[] args) {// 创建一个完全二叉树示例TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right.left = new TreeNode(6);CompleteBinaryTreeCount solution = new CompleteBinaryTreeCount();int nodeCount = solution.countNodes(root);System.out.println("完全二叉树的节点个数: " + nodeCount);}
}
实现总结
- 完全二叉树:完全二叉树的定义是除了最后一层外,其它各层的节点数都达到最大值,且最后一层的节点依次从左到右排列。这一特性对计算节点数有重要影响。
- 确定解题方法:常见的方法包括递归和迭代。在了解完全二叉树的性质后,可以选择合适的方法求解节点数,上面实现就采用了递归的方式实现。
- 确定节点数计算方式:针对完全二叉树的特性,可以通过一些方法,如树的高度、子树的特性等来计算节点数。上面实现通过计算左子树和右子树的高度来确定完全二叉树的结构,如果左右子树高度相等,则左子树是满二叉树,节点个数可以通过2的幂次方计算。如果左右子树高度不等,则递归计算左右子树的节点数。
- 考虑边界情况:对于空树或者只有根节点的情况,需要特殊处理。
- 时间复杂度:
O(log^2 N)。递归的深度为树的高度,每次递归中需要计算左右子树的高度,因此时间复杂度为O(log N),其中 N 为节点个数。在每层递归中,都需要进行一次高度计算,高度计算的时间复杂度也为O(log N),因此总体时间复杂度为O(log^2 N)。
相关文章:
坚持刷题 | 完全二叉树的节点个数
Hello,大家好,我是阿月!坚持刷题,老年痴呆追不上我,今天刷:完全二叉树的节点个数 题目 222.完全二叉树的节点个数 代码实现 class TreeNode {int val;TreeNode left, right;public TreeNode(int val) …...
K8S网络
一、介绍 k8s不提供网络通信,提供了CNI接口(Container Network Interface,容器网络接口),由CNI插件实现完成。 1.1 Pod通信 1.1.1 同一节点Pod通信 Pod通过虚拟Ethernet接口对(Veth Pair)与外部通信,Veth…...
【蓝桥杯51单片机入门记录】LED
目录 一、基础 (1)新建工程 (2)编写前准备 二、LED (1)点亮LED灯 (2)LED闪烁 延时函数的生成(stc-isp中生成) 实现 (3)流水灯…...
轻松使用python将PDF转换为图片(成功)
使用PyMuPDF(fitz)将PDF转换为图片 在处理PDF文件时,我们经常需要将PDF页面转换为图片格式,以便于在网页、文档或应用程序中显示。Python提供了多种方式来实现这一需求,本文将介绍如何使用PyMuPDF(也称为f…...
【目标检测】对DETR的简单理解
【目标检测】对DETR的简单理解 文章目录 【目标检测】对DETR的简单理解1. Abs2. Intro3. Method3.1 模型结构3.2 Loss 4. Exp5. Discussion5.1 二分匹配5.2 注意力机制5.3 方法存在的问题 6. Conclusion参考 1. Abs 两句话概括: 第一个真正意义上的端到端检测器最…...
[工具探索]Safari 和 Google Chrome 浏览器内核差异
最近有些Vue3的项目,使用了safari进行测试环境搞开发,发现页面存在不同程序的页面乱码情况,反而google浏览器没问题,下面我们就对比下他们之间的差异点: 日常开发google chrome占多数;现在主流浏览器 Goog…...
文本生成高清、连贯视频,谷歌推出时空扩散模型
谷歌研究人员推出了创新性文本生成视频模型——Lumiere。 与传统模型不同的是,Lumiere采用了一种时空扩散(Space-time)U-Net架构,可以在单次推理中生成整个视频的所有时间段,能明显增强生成视频的动作连贯性ÿ…...
时隔3年 | 微软 | Windows Server 2025 重磅发布
最新功能 以下是微软产品团队正在努力的方向: Windows Server 2025 为所有人提供的热补丁下一代 AD 活动目录和 SMB数据与存储Hyper-V 和人工智能还有更多… Ignite 发布视频 Windows Server 2025 Ignite Video 介绍 Windows Server 2022 正式发布日期是2021年…...
有趣的css - 动态的毛玻璃背景
页面效果 此效果主要使用 backdrop-filter 属性,以及配合 animation 属性来实现毛玻璃模糊和一些动效。 此效果可适用于登录窗口,网站背景或者一些卡片列表中,使网页更具科技感和空间感。 核心代码部分,简要说明了写法思路&#x…...
桥接模式解析
回调设计模式 意图 回调是指一段可以执行的代码,该代码会被作为参数传递给其他代码,在适当的时候,预期这部分代码将会被调用执行。 解释 案例:我们需要在执行完任务后得到通知。为此,我们会向执行器传递一个回调方法…...
MySQL数据库基础第一篇(SQL通用语法与分类)
文章目录 一、SQL通用语法二、SQL分类三、DDL语句四、DML语句1.案例代码2.读出结果 五、DQL语句1.DQL-基本查询2.DQL-条件查询3.DQL-聚合函数4.DQL-分组查询5.DQL-排序查询6.DQL-分页查询7.DQL语句-执行顺序1.案例代码2.读出结果 六、DCL语句1.DCL-管理用户2.DCL-权限控制1.案例…...
【Qt学习笔记】(一)初识Qt
Qt学习笔记 1 使用Qt Creator 新建项目2 项目代码解释3 创建第一个 Hello World 程序4 关于内存泄漏问题5 Qt 中的对象树6 关于 qDebug()的使用7 使用其他方式创建一个 Hello World 程序(编辑框和按钮方式)8 关于 Qt 中的命名规范…...
YIA主题如何关闭新版本升级提示?WordPress主题怎么取消升级提醒?
前两天YIA主题发布了升级到2.8版本,新增了一些功能,优化调整修复了一些功能,但是这些功能调整幅度不大,加上boke112百科使用的YIA主题已经进行了很多方面的个性化修改,所以就懒得升级了,但是每次进入WordPr…...
消息队列的应用场景
消息队列的应用场景 消息队列中间件是分布式系统中重要的组件,主要解决应用耦合,异步消息,流量削锋等问题实现高性能,高可用,可伸缩和最终一致性架构使用较多的消息队列有ActiveMQ,RabbitMQ,Ze…...
Arcgis10.3安装
所需软件地址 链接:https://pan.baidu.com/s/1aAykUDjkaXjdwFjDvAR83Q?pwdbs2i 提取码:bs2i 1、安装License Manager 点击License Manager.exe,默认下一步。 安装完,点击License Server Administrator,停止服务。…...
用Python和 Cryptography库给你的文件加密解密
用Python和 Cryptography库给你的文件加密解密 用Python和 Cryptography库给你的文件加把安全锁。 先介绍与加密解密有关的几个基本概念。 加密(Encryption):加密是将明文转换为密文的过程,使得未经授权的人无法读懂。 解密&a…...
element-ui button 仿写 demo
基于上篇 button 源码分享写了一个简单 demo,在写 demo 的过程中,又发现了一个小细节,分享一下: 1、组件部分: <template><buttonclass"yss-button"click"handleClick":class"[ty…...
Maya------创建多边形工具
配合导入图像使用 Tab键可以删除一个点! 模型不能超过4边面!多切割工具进行连接! 15.maya常用命令5.创建多边形工具 反转 双显 挤出_哔哩哔哩_bilibili...
SQL分组统计条数时,不存在组类型,如何显示条数为0
首先有张表 CREATE TABLE person (id int NOT NULL AUTO_INCREMENT,name varchar(255) DEFAULT NULL,type int DEFAULT NULL,PRIMARY KEY (id) ) ENGINEInnoDB AUTO_INCREMENT2 DEFAULT CHARSETutf8mb4 COLLATEutf8mb4_0900_ai_ci;表里很简单三条数据: INSERT INT…...
通过日期计算星期函数(C语言版)
测试源代码: #include <stdio.h>int getDayOfWeek(int year, int month, int day) {if (month < 3) {month 12;year--;}int q day;int m month;int K year % 100;int J year / 100;int dayOfWeek (q 13 * (m 1) / 5 K K / 4 J / 4 - 2 * J) % …...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
