【二叉树】Leetcode 222. 完全二叉树的节点个数【简单】
完全二叉树的节点个数
- 你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。
完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例 1:

输入: root = [1,2,3,4,5,6]
输出: 6
解题思路
树的高度:
- 计算树的高度可以在 O(log n) 时间内完成,通过沿着左子树一直走到底。
完全二叉树的性质:
- 对于完全二叉树,如果左右子树的高度相同,那么左子树一定是满二叉树,可以直接计算其节点数;
- 如果左右子树的高度不同,那么右子树一定是满二叉树。
递归计算:
- 根据左右子树的高度关系,递归地计算左右子树的节点数,直到叶节点。
Java实现
public class CountNodes {public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}/** 二叉树的节点数 */public int countNodes(TreeNode root) {if (root == null) {return 0;}int leftDepth = computeDepth(root.left);int rightDepth = computeDepth(root.right);if (leftDepth == rightDepth) {// 左子树是满二叉树return (1 << leftDepth) + countNodes(root.right);} else {// 右子树是满二叉树return (1 << rightDepth) + countNodes(root.left);}}/** 二叉树的深度 */private int computeDepth(TreeNode node) {int depth = 0;while (node != null) {node = node.left;depth++;}return depth;}public static void main(String[] args) {CountNodes countNodes = new CountNodes();// 构建示例完全二叉树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);// 计算完全二叉树的节点个数int result = countNodes.countNodes(root);System.out.println("Number of nodes: " + result); // 输出: 6}
}
时间空间复杂度
- 时间复杂度:O(log n * log n),每次递归调用都减少一半节点,递归的次数logn,且需要计算树的高度logn。
- 空间复杂度:O(log n),递归栈的深度等于树的高度。
相关文章:
【二叉树】Leetcode 222. 完全二叉树的节点个数【简单】
完全二叉树的节点个数 你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。 完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最…...
golang界面设计器,全网少见
今天登录govcl的网站,无意中看到有个简易UI设计器。 对于golang的UI专用设计器,还没在网上真正见过。 之前也用govcl来做过两三个桌面应用,好用是好用,不过要安装Lazarus的IDE来拖动设计UI,还要配置很多东西࿰…...
如何在GlobalMapper中加载高清卫星影像?
GlobalMapper在GIS行业几乎无人不知,无人不晓,但它可以直接加载卫星影像也许就不是每个人都知道的了。 这里就来分享一下如何在GlobalMapper中加载高清卫星影像,并可以在文末查看领取软件安装包和图源的方法。 如何加载高清图源 首先&…...
【机器学习】解锁AI密码:神经网络算法详解与前沿探索
👀传送门👀 🔍引言🍀神经网络的基本原理🚀神经网络的结构📕神经网络的训练过程🚆神经网络的应用实例💖未来发展趋势💖结语 🔍引言 随着人工智能技术的飞速发…...
Java如何实现pdf转base64以及怎么反转?
问题需求 今天在做发送邮件功能的时候,发现邮件的附件部分,比如pdf文档,要求先把pdf转为base64,邮件才会发送。那接下来就先看看Java 如何把 pdf文档转为base64。 两种方式,一种是通过插件 jar 包的方式引入…...
动态规划5:62. 不同路径
动态规划解题步骤: 1.确定状态表示:dp[i]是什么 2.确定状态转移方程:dp[i]等于什么 3.初始化:确保状态转移方程不越界 4.确定填表顺序:根据状态转移方程即可确定填表顺序 5.确定返回值 题目链接:62. …...
Python编程学习第一篇——Python零基础快速入门(五)-列表(List)
今天我们来一起学习Python的列表(list),Python中的列表(List)是一种有序、可变的数据结构,可以用来存储多个值。列表可以包含不同类型的数据,例如整数、浮点数、字符串等。以下是关于Python列表…...
c# - 运算符 << 不能应用于 long 和 long 类型的操作数
Compiler Error CS0019 c# - 运算符 << 不能应用于 long 和 long 类型的操作数 处理方法 特此记录 anlog 2024年5月30日...
问题排查|记录一次基于mymuduo库开发的服务器错误排查(回响服务器无法正常工作)
问题背景: 服务器程序如下: #include <mymuduo/TcpServer.h> #include <mymuduo/Logger.h>#include <string> #include <functional>class EchoServer { public:EchoServer(EventLoop *loop,const InetAddress &addr, con…...
中介模式实现聊天室
中介者模式的核心逻辑就是解耦对象‘多对多’的相互依赖关系。当遇到一大堆混乱的对象呈现“网状结构”,利用通过中介者模式解耦对象之间的通讯。 代码案例 抽象中介类 public abstract class AbstractChatRoom {public abstract void notice(String message , Us…...
游戏开发与游戏设计区别
游戏设计与游戏开发是两个紧密相关但有着不同重点的领域,通常需要不同的技能和流程。以下是对游戏设计与游戏开发的详细解释,以及两者的区别: 游戏设计是关于构思和规划游戏的内容、机制和体验的过程。 主要内容: 故事和情节:构…...
卡尔曼滤波算法的matlab实现
卡尔曼滤波算法的matlab实现 figure; hold on;Z(1:1:100); %观测值:第一秒观测1m 第二秒观测两米 匀速运动, 每秒1m, 最后拟合的也是速度 1m/splot(Z); plot([0,100], [1,1]);noiserandn(1,100)*0.5; %生成方差为1的高斯噪声 ZZnoise; % 加入噪声plot(Z);X[0;…...
Unity Obi Rope失效
文章目录 前言一、WebGL端Obi Rope失效二、Obi Rope 固定不牢三、使用Obi后卡顿总结 前言 Obi 是一款基于粒子的高级物理引擎,可模拟各种可变形材料的行为。 使用 Obi Rope,你可以在几秒内创建绳索和杆子,同时完全控制它们的形状和行为&…...
基于Nginx和Consul构建自动发现的Docker服务架构——非常之详细
基于Nginx和Consul构建自动发现的Docker服务架构 文章目录 基于Nginx和Consul构建自动发现的Docker服务架构资源列表基础环境一、安装Docker1.1、Consul节点安装1.2、registrator节点安装 二、案例前知识点2.1、什么是Consul 三、基于Nginx和Consul构建自动发现的Docker服务架构…...
Gnu/Linux 系统编程 - 如何获取帮助及一个演示
Gnu/Linux 系统编程 - 如何获取帮助及一个演示 今天开始写 Gnu/Linux 环境下的系统编程,主要的用的语言是 C,主要是为了学习 C 语言,边学边写,这样的学习速度是比较快的。 今天就先介绍下如何在手头上没有任何资料的情况下&…...
ffmpeg 的sws_scale接口函数解析
ffmpeg 的 sws_scale 函数是 libswscale 库中的一个重要函数,用于进行图像的缩放和颜色空间转换。它的主要作用是将输入图像帧转换为另一种尺寸或颜色格式的输出图像帧。下面详细解析一下 sws_scale 函数的作用、参数等。 sws_scale 函数的作用 ffmpeg 的 sws_sca…...
MoonBit 本周新增类型标注语法、继续进行核心库 API 整理工作
MoonBit更新 类型标注增加了新的语法T? 来表示Option[T] struct Cell[T] {val: Tnext: Cell[T]? }fn f(x : Cell[T]?) -> Unit { ... }相当于 struct Cell[T] {val: Tnext: Option[Cell[T]] }fn f(x : Option[Cell[T]]) -> Unit { ... }旧的Option[T]仍然兼容&…...
YOLOv10训练自己的数据集
目录 0、引言 1、环境配置 2、数据集准备 3、创建配置文件 3.1、设置官方配置文件:default.yaml,可自行修改。 3.2、设置data.yaml 4、进行训练 4.1、方法一 4.2、方法二 5、验证模型 5.1、命令行输入 5.2、脚本运行 6、总结 0、引言 本文…...
探索Web前端三大主流框架:Angular、React和Vue.js
探索Web前端三大主流框架:Angular、React和Vue.js 在现代Web开发中,前端框架已经成为开发者构建复杂应用的重要工具。Angular、React和Vue.js是目前最受欢迎的三大前端框架,它们各具特色,适用于不同的开发需求。本文将详细介绍这…...
《HelloGitHub》第 98 期
兴趣是最好的老师,HelloGitHub 让你对编程感兴趣! 简介 HelloGitHub 分享 GitHub 上有趣、入门级的开源项目。 github.com/521xueweihan/HelloGitHub 这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等,涵盖多种编程语言 Python、…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
