面试经典 222. 完全二叉树的节点个数
-
二叉树我最近刷的特别多,差不多快刷完了,但是有一种题型差点给我忽略了,那就是完全二叉树,这也是一个很重要的题型,今天刚好有一道题目可以来复习一下完全二叉树的特性
-
题目链接如下:https://leetcode.cn/problems/count-complete-tree-nodes/?envType=study-plan-v2&envId=top-interview-150

-
做这道题首先有一点要知道的,就是完全二叉树是怎么样子的,下面说一下完全二叉树的概念
-
完全二叉树:只有最底层的节点未被填满,且最底层节点尽量靠左填充

-
ok 现在已经了解了基础概念了,我们再来看这道题目
-
这道题目的目的是让我们遍历这棵树,并算有几个节点
-
说实话,这道题很简单,用暴力的做法,就是遍历一整棵树,代码如下:
-
递归法:
//方法一:递归
func Solution222(root *TreeNode) int {if root == nil {return 0}left := Solution222(root.Left)right := Solution222(root.Right)return left + right + 1
}
- 迭代法:
//方法二:迭代
func Solution222v2(root *TreeNode) int {if root == nil{return 0}queue := []*TreeNode{root}count := 0for len(queue) > 0{node := queue[0]queue = queue[1:]count++if node.Left != nil{queue = append(queue, node.Left)}if node.Right != nil{queue = append(queue, node.Right)}}return count
}
-
这两个方法是遍历树的最基本的方法之一
-
但是 这不是这道题的本意,这道题目是想要我们理由完全二叉树这个特性解题
-
那我们需要好好思考一下,完全二叉树有什么特点
-
除了最后的叶子节点,其他层级节点都是满的
-
当 左子树的深度 和 右子树的深度 一致的时候,说明 左子树是满的二叉树 可以通过 2的h次方求的左子树的节点个数

-
当 右子树的深度 不如 左子树的深度 的时候,说明 左子树不是一个满的二叉树,但是右子树单独看是一个满的二叉树,所以可以通过 2的h次方求右子树的节点个数

-
-
ok,知道这些特点,我们是不是可以利用一个逻辑来减少遍历
- 当 左子树深度 等于 右子树的时候,就可以通过深度来计算左子树的节点,然后只遍历右子树
- 当 左子树深度 等于 右子树的时候,就可以通过深度来计算右子树的节点,然后只遍历左子树
-
这样我们本来需要遍历全部二叉树节点的,现在只需要遍历一半,思路瞬间打开,代码如下:
//方法三:二分查找
func Solution222v3(root *TreeNode) int {if root == nil{return 0}//检索左子树深度left := root.Leftldepth := 0for left != nil{left = left.Leftldepth++}//检索右子树深度right := root.Rightrdepth := 0for right != nil{right = right.Leftrdepth++}//左右子树深度判断if ldepth == rdepth{return (1<<ldepth) + Solution222v3(root.Right)}else{return (1<<rdepth) + Solution222v3(root.Left)}
}
ok,这里这道题目就结束了,感谢大家观看
相关文章:
面试经典 222. 完全二叉树的节点个数
二叉树我最近刷的特别多,差不多快刷完了,但是有一种题型差点给我忽略了,那就是完全二叉树,这也是一个很重要的题型,今天刚好有一道题目可以来复习一下完全二叉树的特性 题目链接如下:https://leetcode.cn/…...
【css】3d柱状图-vue组件版
创建一个响应式圆柱形进度条组件 在现代网页设计中,圆柱形进度条是一种非常流行的视觉元素,用于展示数据的进度或状态。本文将介绍如何使用Vue.js和LESS创建一个响应式的圆柱形进度条组件。 组件结构 我们的组件由两部分组成:一个圆柱形的…...
《计算机组成原理》(第3版)第3章 系统总线 复习笔记
第3章 系统总线 一、总线的基本概念 总线是连接多个部件的信息传输线,是各部件共享的传输介质,如图3-1所示。 图3-1 面向CPU的双总线结构框图 倘若将CPU、主存和I/O设备都挂到一组总线上,便形成单总线结构的计算机,如图3-2所示…...
【网络安全】https协议的加密方案避免中间人攻击(MITM攻击)导致的数据泄露风险
目录 引言 概念准备 中间人 加密 数据摘要 && 数据指纹 数字签名 密钥加密 中间人攻击 CA证书 https加密的解决方案 个人主页:东洛的克莱斯韦克-CSDN博客 引言 http在应用层协议中是明文传输协议,它是通信双方传输数据时的一种约定。【…...
拼多多商家电话采集 拼多多店铺爬虫软件使用教程
拼多多商家电话采集和店铺爬虫软件使用教程: 商家电话采集: a. 打开拼多多网站,进入需要采集电话号码的店铺页面。 b. 打开浏览器开发者工具(一般按F12键或右键选择“检查”)。 c. 在开发者工具中切换到“网络”或“Ne…...
RK3566 MIPI屏调试记录
文章目录 1. 前言2. 环境介绍3. 思路介绍4. 确认要修改的设备树文件5. 设备树中修改关键引脚5.1. 添加dsi0节点5.2. 修改屏幕背光引脚5.3. 添加屏幕复位引脚5.4. 添加屏幕使能引脚 6. 修改屏幕timing参数7. 修改上下电时序8. 修改初始化序列和反初始化序列9. 显示路由配置10. 最…...
爬虫数据模拟真实设备请求头User-Agent生成(fake_useragent:一个超强的Python库)
在Python开发中,处理HTTP请求时经常需要模拟不同的用户代理(User-Agent)来绕过网站的反爬虫机制或进行兼容性测试。fake_useragent正是这样一个强大的Python库,它能够生成随机且多样化的用户代理字符串,让你的请求看起…...
【教育宝-注册安全分析报告】
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 暴力破解密码,造成用户信息泄露短信盗刷的安全问题,影响业务及导致用户投诉带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞…...
3.达梦数据库基础运维管理
文章目录 前言一、基础数据库管理权限角色管理1.1 DM 系统管理员的类型1.2 角色责则分类 DM 数据库2.1 数据库评估2.2 状态和模式 参考内容 前言 本篇博客为上一篇博客的进阶版,主要针对常规达梦数据库的基本管理上面 一、基础数据库管理 权限角色管理 1.1 DM 系…...
【Linux】【系统纪元】Linux起源与环境安装
快乐的流畅:个人主页 个人专栏:《C游记》《进击的C》《Linux迷航》 远方有一堆篝火,在为久候之人燃烧! 文章目录 一、Linux的起源1.1 计算机硬件1.2 计算机软件 二、Linux的环境安装2.1 安装方式2.2 安装版本2.3 安装过程2.4 远程…...
Android笔试面试题AI答之Activity(9)
文章目录 1.如何在Application中获取当前Activity实例 ?方法一:使用全局变量或单例方法二:使用LocalBroadcastManager或EventBus方法三:通过Fragment方法四:使用Service和Intent注意事项 2.Activity A跳转Activity B&a…...
什么是嵌入式
1、什么是嵌入式 对专用设备的控制,把不需要的功能能够裁剪、删除,适配于专用设备,就叫做嵌入式(也叫做嵌入式系统) 嵌入式系统定义:用于控制、监视或者辅助机器和设备的运行 一个嵌入式系统由硬件和软件…...
SAM 2:Segment Anything in Images and Videos 论文详解
SAM 2:Segment Anything in Images and Videos 文章目录 SAM 2:Segment Anything in Images and Videos摘要1 Introduction具体分析 2 Related work具体分析: 3 任务:可提示的视觉分割4 模型具体分析具体分析 5 数据5.1 Data engine5.2 SA - V数据集 6 Z…...
PYTHON专题-(10)基操之我要玩并发
什么是并发? 并发指的是两个或多个事件在同一时间间隔内发生。在计算机科学中,并发通常指的是一个程序同时执行多个独立的任务。这些任务可以同时进行,而不会相互干扰或阻塞彼此。并发可以提高程序的执行效率和资源利用率,但也需要…...
双指针实现删除字符串中的所有相邻重复项
class Solution:def removeDuplicates(self, s: str) -> str:res list(s)slow fast 0length len(res)while fast < length:# 如果一样直接换,不一样会把后面的填在slow的位置res[slow] res[fast]# 如果发现和前一个一样,就退一格指针if slow …...
vue(vue2和vue3)项目打包去除console.log
1.Vue2去除 module.exports { configureWebpack: (config) > {// 取消console打印config.optimization.minimizer[0].options.terserOptions.compress.drop_console truereturn {name: "项目名称",resolve: {alias: {"": resolve("src")}}…...
Visual Studio 2022社区版、专业版、企业版功能对比表
https://visualstudio.microsoft.com/zh-hans/vs/compare/...
Codeforces 888 div3 A-G
A. Escalator Conversations 分析 二者身高差为k的倍数且不超过m-1倍,身高差不能为0(即不能在同一个阶梯) C代码 #include<iostream> using namespace std; void solve(){int n,m,k,H,ans0;cin>>n>>m>>k>>H;…...
IDEA如何去掉编辑框右侧的竖线
打开 IntelliJ Idea 软件 依次找到 File—>Settings—>Editor—>General—>Appearance 去掉勾选 Show hard wrap and visual guides (configured in Code Style options)...
3DCoat v2023 激活版下载与安装教程 (数字雕刻程序)
前言 3DCoat 是一款数字雕塑软件,由乌克兰开发。该软件专注于游戏模型的细节设计,集三维模型实时纹理绘制和细节雕刻功能为一身,可以加速细节设计流程,在更短的时间内创造出更多的内容。 一、下载地址 下载链接:分享…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
高防服务器价格高原因分析
高防服务器的价格较高,主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因: 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器,因此…...
02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...
命令行关闭Windows防火墙
命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)方法二:CMD命令…...
raid存储技术
1. 存储技术概念 数据存储架构是对数据存储方式、存储设备及相关组件的组织和规划,涵盖存储系统的布局、数据存储策略等,它明确数据如何存储、管理与访问,为数据的安全、高效使用提供支撑。 由计算机中一组存储设备、控制部件和管理信息调度的…...
