【二叉树】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、…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
