C++力扣题目222--完全二叉树的节点个数

news/2024/2/23 13:42:59/文章来源:https://blog.csdn.net/weixin_47675625/article/details/135525122

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

示例 1:

输入:root = [1,2,3,4,5,6]
输出:6

示例 2:

输入:root = []
输出:0

示例 3:

输入:root = [1]
输出:1

提示:

  • 树中节点的数目范围是[0, 5 * 104]
  • 0 <= Node.val <= 5 * 104
  • 题目数据保证输入的树是 完全二叉树

思路

本篇给出按照普通二叉树的求法以及利用完全二叉树性质的求法。

#普通二叉树

首先按照普通二叉树的逻辑来求。

这道题目的递归法和求二叉树的深度写法类似, 而迭代法,二叉树:层序遍历登场! (opens new window)遍历模板稍稍修改一下,记录遍历的节点数量就可以了。

递归遍历的顺序依然是后序(左右中)。

#递归

如果对求二叉树深度还不熟悉的话,看这篇:二叉树:看看这些树的最大深度 (opens new window)。

  1. 确定递归函数的参数和返回值:参数就是传入树的根节点,返回就返回以该节点为根节点二叉树的节点数量,所以返回值为int类型。

代码如下:

int getNodesNum(TreeNode* cur) {

  1. 确定终止条件:如果为空节点的话,就返回0,表示节点数为0。

代码如下:

if (cur == NULL) return 0;

  1. 确定单层递归的逻辑:先求它的左子树的节点数量,再求右子树的节点数量,最后取总和再加一 (加1是因为算上当前中间节点)就是目前节点为根节点的节点数量。

代码如下:

int leftNum = getNodesNum(cur->left);      // 左
int rightNum = getNodesNum(cur->right);    // 右
int treeNum = leftNum + rightNum + 1;      // 中
return treeNum;

所以整体C++代码如下:

// 版本一
class Solution {
private:int getNodesNum(TreeNode* cur) {if (cur == NULL) return 0;int leftNum = getNodesNum(cur->left);      // 左int rightNum = getNodesNum(cur->right);    // 右int treeNum = leftNum + rightNum + 1;      // 中return treeNum;}
public:int countNodes(TreeNode* root) {return getNodesNum(root);}
};

代码精简之后C++代码如下:

// 版本二
class Solution {
public:int countNodes(TreeNode* root) {if (root == NULL) return 0;return 1 + countNodes(root->left) + countNodes(root->right);}
};

  • 时间复杂度:O(n)
  • 空间复杂度:O(log n),算上了递归系统栈占用的空间

网上基本都是这个精简的代码版本,其实不建议大家照着这个来写,代码确实精简,但隐藏了一些内容,连遍历的顺序都看不出来,所以初学者建议学习版本一的代码,稳稳的打基础

#迭代

如果对求二叉树层序遍历还不熟悉的话,看这篇:二叉树:层序遍历登场! (opens new window)。

那么只要模板少做改动,加一个变量result,统计节点数量就可以了

class Solution {
public:int countNodes(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result = 0;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();result++;   // 记录节点数量if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return result;}
};

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

#完全二叉树

以上方法都是按照普通二叉树来做的,对于完全二叉树特性不了解的同学可以看这篇 关于二叉树,你该了解这些! (opens new window),这篇详细介绍了各种二叉树的特性。

在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1)  个节点。

大家要自己看完全二叉树的定义,很多同学对完全二叉树其实不是真正的懂了。

我来举一个典型的例子如题:

完全二叉树只有两种情况,情况一:就是满二叉树,情况二:最后一层叶子节点没有满。

对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1。

对于情况二,分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况1来计算。

完全二叉树(一)如图: 

222.完全二叉树的节点个数

完全二叉树(二)如图: 

222.完全二叉树的节点个数1

可以看出如果整个树不是满二叉树,就递归其左右孩子,直到遇到满二叉树为止,用公式计算这个子树(满二叉树)的节点数量。

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢?

在完全二叉树中,如果递归向左遍历的深度等于递归向右遍历的深度,那说明就是满二叉树。如图:

在完全二叉树中,如果递归向左遍历的深度不等于递归向右遍历的深度,则说明不是满二叉树,如图:

那有录友说了,这种情况,递归向左遍历的深度等于递归向右遍历的深度,但也不是满二叉树,如题:

如果这么想,大家就是对 完全二叉树理解有误区了,以上这棵二叉树,它根本就不是一个完全二叉树

判断其子树是不是满二叉树,如果是则利用公式计算这个子树(满二叉树)的节点数量,如果不是则继续递归,那么 在递归三部曲中,第二部:终止条件的写法应该是这样的:

if (root == nullptr) return 0; 
// 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便
while (left) {  // 求左子树深度left = left->left;leftDepth++;
}
while (right) { // 求右子树深度right = right->right;rightDepth++;
}
if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2,返回满足满二叉树的子树节点数量
}

递归三部曲,第三部,单层递归的逻辑:(可以看出使用后序遍历)

int leftTreeNum = countNodes(root->left);       // 左
int rightTreeNum = countNodes(root->right);     // 右
int result = leftTreeNum + rightTreeNum + 1;    // 中
return result;

该部分精简之后代码为:

return countNodes(root->left) + countNodes(root->right) + 1; 

最后整体C++代码如下:

class Solution {
public:int countNodes(TreeNode* root) {if (root == nullptr) return 0;TreeNode* left = root->left;TreeNode* right = root->right;int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的,为了下面求指数方便while (left) {  // 求左子树深度left = left->left;leftDepth++;}while (right) { // 求右子树深度right = right->right;rightDepth++;}if (leftDepth == rightDepth) {return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2,所以leftDepth初始为0}return countNodes(root->left) + countNodes(root->right) + 1;}
};
  • 时间复杂度:O(log n × log n)
  • 空间复杂度:O(log n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_925289.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

springCould中的Stream-从小白开始【12】

&#x1f95a;今日鸡汤&#x1f95a; 见过一些人&#xff0c;他们朝九晚五&#x1f62d;&#xff0c;有时也要加班&#xff0c;却能把生活过得很&#x1f60e;有趣。他们有自己的爱好&#xff0c;不怕独处。他们有自己的坚持&#xff0c;哪怕没人在乎。&#x1f926;‍♂️ 开心…

电脑/设备网络共享给其他设备上网

文章目录 一、概述二、设置网络共享2.1 电脑可以上网&#xff0c;通过网络共享让其他设备也可以上网2.2 手机如何使用USB数据线共享网络给电脑 一、概述 现在有如下几种情况&#xff1a; 设备本身不能上网&#xff0c;需要通过电脑上网 笔记本WIFI连热点上网&#xff0c;然后…

【贪心】重构字符串

/*** 思路&#xff1a;如果s长度小于2&#xff0c;直接返回s&#xff0c;假设字符串s的长度为n。* n为偶数&#xff0c;如果字符串中的某个字符数量超过 n/2 则肯定会存在相邻的字符。* n为奇数&#xff0c;如果字符串中的某个字符的数量超过 &#xff08;n1&am…

响应式Web开发项目教程(HTML5+CSS3+Bootstrap)第2版 第1章 HTML5+CSS3初体验 项目1-1 三栏布局页面

项目展示 三栏布局是一种常用的网页布局结构。 除了头部区域、底部区域外&#xff0c;中间的区域&#xff08;主体区域&#xff09;划分成了三个栏目&#xff0c;分别是左侧边栏、内容区域和右侧边栏&#xff0c;这三个栏目就构成了三栏布局。当浏览器的宽度发声变化时&#x…

十四.变量、异常处理

变量、异常处理 1.变量1.1系统变量1.1.1系统变量分类1.1.2查看系统变量 1.2用户变量1.2.1用户变量分类1.2.2会话用户变量1.2.3局部变量1.2.4对比会话用户变量与局部变量 补充:MySQL 8.0的新特性—全局变量的持久化 2.定义条件与处理程序2.1案例分析2.2定义条件2.3定义处理程序2…

设计模式-- 3.适配器模式

适配器模式 将一个类的接口转换成客户希望的另外一个接口。使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。 角色和职责 请求者&#xff08;client&#xff09;&#xff1a;客户端角色,需要使用适配器的对象&#xff0c;不需要关心适配器内部的实现&#xff0c;…

坑记(HttpInputMessage)

一、背景知识 public interface HttpInputMessage extends HttpMessage Represents an HTTP input message, consisting of headers and a readable body.Typically implemented by an HTTP request on the server-side, or a response on the client-side.Since: 3.0 Author:…

【JaveWeb教程】(26) Mybatis基础操作(新增、修改、查询、删除) 详细代码示例讲解(最全面)

目录 1. Mybatis基础操作1.1 需求1.2 准备1.3 删除1.3.1 功能实现1.3.2 日志输入1.3.3 预编译SQL1.3.3.1 介绍1.3.3.2 SQL注入1.3.3.3 参数占位符 1.4 新增1.4.1 基本新增1.4.2 主键返回 1.5 更新1.6 查询1.6.1 根据ID查询1.6.2 数据封装1.6.3 条件查询1.6.4 参数名说明 1. Myb…

Redis集群Cluster和分片

1.Cluster集群介绍 背景 Sentinel解决了主从架构故障自动迁移的问题但是master主节点的写能力和存储能力依旧受限使用Redis的集群Cluster就是为了解决单机Redis容量有限的问题&#xff0c;将数据按一定的规则分配到多台机器 什么是集群Cluster 是一组相互独立的、通过告诉网络…

ssm基于Java的药店药品信息管理系统的设计与实现论文

摘 要 传统信息的管理大部分依赖于管理人员的手工登记与管理&#xff0c;然而&#xff0c;随着近些年信息技术的迅猛发展&#xff0c;让许多比较老套的信息管理模式进行了更新迭代&#xff0c;药品信息因为其管理内容繁杂&#xff0c;管理数量繁多导致手工进行处理不能满足广大…

布隆过滤器四种实现(Java,Guava,hutool,Redisson)

1.背景 为预防大量黑客故意发起非法的时间查询请求&#xff0c;造成缓存击穿&#xff0c;建议采用布隆过滤器的方法解决。布隆过滤器通过一个很长的二进制向量和一系列随机映射函数&#xff08;哈希函数&#xff09;来记录与识别某个数据是否在一个集合中。如果数据不在集合中…

Alibaba-> EasyExcel 整理3

1 导入依赖 <!-- easyExcel --><dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version >3.2.1</version><exclusions><exclusion><artifactId>poi-ooxml-schemas</art…

SQL-分页查询and语句执行顺序

&#x1f389;欢迎您来到我的MySQL基础复习专栏 ☆* o(≧▽≦)o *☆哈喽~我是小小恶斯法克&#x1f379; ✨博客主页&#xff1a;小小恶斯法克的博客 &#x1f388;该系列文章专栏&#xff1a;重拾MySQL &#x1f379;文章作者技术和水平很有限&#xff0c;如果文中出现错误&am…

LLVM系列(1): 在微软Visual Studio下编译LLVM

参考链接&#xff1a; Getting Started with the LLVM System using Microsoft Visual Studio — LLVM 18.0.0git documentation 1.安装visualstudio&#xff0c;版本需要大于vs2019 本机环境已安装visual studio2022&#xff0c;省略 2安装Makefile&#xff0c;版本需要大…

【K8s学习】

k8s的简单执行流程&#xff1a; Kubernetes Master&#xff08;API Server、Scheduler等组件&#xff09;负责调度Pod到合适的Node上。 当Pod被调度到某个Node时&#xff0c;该Node上的kubelet代理会收到指令并开始执行Pod的生命周期管理任务&#xff0c;包括创建、监控和终止P…

【Python数据可视化】matplotlib之绘制常用图形:折线图、柱状图(条形图)、饼图和直方图

文章传送门 Python 数据可视化matplotlib之绘制常用图形&#xff1a;折线图、柱状图&#xff08;条形图&#xff09;、饼图和直方图matplotlib之设置坐标&#xff1a;添加坐标轴名字、设置坐标范围、设置主次刻度、坐标轴文字旋转并标出坐标值matplotlib之增加图形内容&#x…

阿里 P7 三面凉凉,kafka Borker 日志持久化没答上来

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱敲代码的小黄&#xff0c;阿里巴巴淘天Java开发工程师&#xff0c;CSDN博客专家&#x1f4d5;系列专栏&#xff1a;Spring源码、Netty源码、Kafka源码、JUC源码、dubbo源码系列&#x1f525;如果感觉博主的文章还不错…

JVM基础(7)——ParNew垃圾回收器

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 学习必须往深处挖&…

市场复盘总结 20240116

仅用于记录当天的市场情况&#xff0c;用于统计交易策略的适用情况&#xff0c;以便程序回测 短线核心&#xff1a;不参与任何级别的调整&#xff0c;采用龙空龙模式 昨日主题投资 连板进级率 18% 二进三&#xff1a; 进级率低 60% 最常用的二种方法&#xff1a; 方法一&am…

【iOS】数据持久化(四)之FMDB基本使用

正如我们前面所看到的&#xff0c;原生SQLite API在使用时还是比较麻烦的&#xff0c;于是&#xff0c;开源社区就出现了一系列将SQLite API进行封装的库&#xff0c;其中FMDB的被大多数人所使用 FMDB和SQLite相比较&#xff0c;SQLite比较原始&#xff0c;操作比较复杂&#…