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

坚持刷题 | 完全二叉树的节点个数

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&#xff0c;大家好&#xff0c;我是阿月&#xff01;坚持刷题&#xff0c;老年痴呆追不上我&#xff0c;今天刷&#xff1a;完全二叉树的节点个数 题目 222.完全二叉树的节点个数 代码实现 class TreeNode {int val;TreeNode left, right;public TreeNode(int val) …...

K8S网络

一、介绍 k8s不提供网络通信&#xff0c;提供了CNI接口(Container Network Interface&#xff0c;容器网络接口)&#xff0c;由CNI插件实现完成。 1.1 Pod通信 1.1.1 同一节点Pod通信 Pod通过虚拟Ethernet接口对&#xff08;Veth Pair&#xff09;与外部通信&#xff0c;Veth…...

【蓝桥杯51单片机入门记录】LED

目录 一、基础 &#xff08;1&#xff09;新建工程 &#xff08;2&#xff09;编写前准备 二、LED &#xff08;1&#xff09;点亮LED灯 &#xff08;2&#xff09;LED闪烁 延时函数的生成&#xff08;stc-isp中生成&#xff09; 实现 &#xff08;3&#xff09;流水灯…...

轻松使用python将PDF转换为图片(成功)

使用PyMuPDF&#xff08;fitz&#xff09;将PDF转换为图片 在处理PDF文件时&#xff0c;我们经常需要将PDF页面转换为图片格式&#xff0c;以便于在网页、文档或应用程序中显示。Python提供了多种方式来实现这一需求&#xff0c;本文将介绍如何使用PyMuPDF&#xff08;也称为f…...

【目标检测】对DETR的简单理解

【目标检测】对DETR的简单理解 文章目录 【目标检测】对DETR的简单理解1. Abs2. Intro3. Method3.1 模型结构3.2 Loss 4. Exp5. Discussion5.1 二分匹配5.2 注意力机制5.3 方法存在的问题 6. Conclusion参考 1. Abs 两句话概括&#xff1a; 第一个真正意义上的端到端检测器最…...

[工具探索]Safari 和 Google Chrome 浏览器内核差异

最近有些Vue3的项目&#xff0c;使用了safari进行测试环境搞开发&#xff0c;发现页面存在不同程序的页面乱码情况&#xff0c;反而google浏览器没问题&#xff0c;下面我们就对比下他们之间的差异点&#xff1a; 日常开发google chrome占多数&#xff1b;现在主流浏览器 Goog…...

文本生成高清、连贯视频,谷歌推出时空扩散模型

谷歌研究人员推出了创新性文本生成视频模型——Lumiere。 与传统模型不同的是&#xff0c;Lumiere采用了一种时空扩散&#xff08;Space-time&#xff09;U-Net架构&#xff0c;可以在单次推理中生成整个视频的所有时间段&#xff0c;能明显增强生成视频的动作连贯性&#xff…...

时隔3年 | 微软 | Windows Server 2025 重磅发布

最新功能 以下是微软产品团队正在努力的方向&#xff1a; Windows Server 2025 为所有人提供的热补丁下一代 AD 活动目录和 SMB数据与存储Hyper-V 和人工智能还有更多… Ignite 发布视频 Windows Server 2025 Ignite Video 介绍 Windows Server 2022 正式发布日期是2021年…...

有趣的css - 动态的毛玻璃背景

页面效果 此效果主要使用 backdrop-filter 属性&#xff0c;以及配合 animation 属性来实现毛玻璃模糊和一些动效。 此效果可适用于登录窗口&#xff0c;网站背景或者一些卡片列表中&#xff0c;使网页更具科技感和空间感。 核心代码部分&#xff0c;简要说明了写法思路&#x…...

桥接模式解析

回调设计模式 意图 回调是指一段可以执行的代码&#xff0c;该代码会被作为参数传递给其他代码&#xff0c;在适当的时候&#xff0c;预期这部分代码将会被调用执行。 解释 案例&#xff1a;我们需要在执行完任务后得到通知。为此&#xff0c;我们会向执行器传递一个回调方法…...

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&#xff08;&#xff09;的使用7 使用其他方式创建一个 Hello World 程序&#xff08;编辑框和按钮方式&#xff09;8 关于 Qt 中的命名规范…...

YIA主题如何关闭新版本升级提示?WordPress主题怎么取消升级提醒?

前两天YIA主题发布了升级到2.8版本&#xff0c;新增了一些功能&#xff0c;优化调整修复了一些功能&#xff0c;但是这些功能调整幅度不大&#xff0c;加上boke112百科使用的YIA主题已经进行了很多方面的个性化修改&#xff0c;所以就懒得升级了&#xff0c;但是每次进入WordPr…...

消息队列的应用场景

消息队列的应用场景 消息队列中间件是分布式系统中重要的组件&#xff0c;主要解决应用耦合&#xff0c;异步消息&#xff0c;流量削锋等问题实现高性能&#xff0c;高可用&#xff0c;可伸缩和最终一致性架构使用较多的消息队列有ActiveMQ&#xff0c;RabbitMQ&#xff0c;Ze…...

Arcgis10.3安装

所需软件地址 链接&#xff1a;https://pan.baidu.com/s/1aAykUDjkaXjdwFjDvAR83Q?pwdbs2i 提取码&#xff1a;bs2i 1、安装License Manager 点击License Manager.exe&#xff0c;默认下一步。 安装完&#xff0c;点击License Server Administrator&#xff0c;停止服务。…...

用Python和 Cryptography库给你的文件加密解密

用Python和 Cryptography库给你的文件加密解密 用Python和 Cryptography库给你的文件加把安全锁。 先介绍与加密解密有关的几个基本概念。 加密&#xff08;Encryption&#xff09;&#xff1a;加密是将明文转换为密文的过程&#xff0c;使得未经授权的人无法读懂。 解密&a…...

element-ui button 仿写 demo

基于上篇 button 源码分享写了一个简单 demo&#xff0c;在写 demo 的过程中&#xff0c;又发现了一个小细节&#xff0c;分享一下&#xff1a; 1、组件部分&#xff1a; <template><buttonclass"yss-button"click"handleClick":class"[ty…...

Maya------创建多边形工具

配合导入图像使用 Tab键可以删除一个点&#xff01; 模型不能超过4边面&#xff01;多切割工具进行连接&#xff01; 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;表里很简单三条数据&#xff1a; INSERT INT…...

通过日期计算星期函数(C语言版)

测试源代码&#xff1a; #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) % …...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...