【二叉树算法题记录】222. 完全二叉树的节点个数

embedded/2024/9/24 12:16:07/

题目描述

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

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

题目分析

迭代法

简单暴力直接上层次遍历!(万能的层次遍历)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {// 层次遍历queue<TreeNode*> q;if(root!=NULL) q.push(root);int num = 0;    // 节点个数numwhile(!q.empty()){int size = q.size();while(size--){  // 遍历每层节点TreeNode* node = q.front();q.pop();num++;// 放入该节点下层的左右孩子if(node->left) q.push(node->left);if(node->right) q.push(node->right);}}return num;}
};

递归法

递归计算左右子树的结点个数,然后合并。

class Solution {
public:int countNodes(TreeNode* root) {// 递归遍历:每一层都在计算子树的节点数量// 递归终止条件:if(root==NULL) return 0;int left = countNodes(root->left);int right = countNodes(root->right);int total = left + right + 1;return total;}
};

不过这题有个特殊条件:完全二叉树。完全二叉树有两种情况,一种是满二叉树,另一种是最后一层叶子节点不是满的。我们知道,满二叉树的节点数是很好计算的,也就是 2 n − 1 2^n-1 2n1 n n n是深度。那么我们可以利用递归计算寻找到的满二叉树的节点数量,一层一层传上来,就得到了整体完全二叉树的节点数量。

class Solution {
public:int countNodes(TreeNode* root) {// 递归法// 递归终止条件if(root==NULL) return 0;TreeNode* left = root->left;TreeNode* right = root->right;int leftDepth = 0, rightDepth = 0;while(left) {left = left->left;leftDepth++;}while(right){right = right->right;rightDepth++;}if(leftDepth==rightDepth){  // 判断当前子树是不是满二叉树,即左右深度相同// 如果是满二叉树,则返回节点个数return (2 << leftDepth) - 1;}// 单层递归逻辑return countNodes(root->left) + countNodes(root->right) + 1;}
};

http://www.ppmy.cn/embedded/35901.html

相关文章

革新食品改良,解锁品质新高度——体验西奥机电TEX-01质构仪的卓越魅力

革新食品改良&#xff0c;解锁品质新高度——体验西奥机电TEX-01质构仪的卓越魅力 引领食品改良新潮流 在追求品质生活的今天&#xff0c;食品的口感和品质成为了消费者选择的重要标准。为了满足这一市场需求&#xff0c;食品企业正积极寻求新的改良方法&#xff0c;以提升产…

继承知识及扩展(C++)

1. 继承是什么&#xff1f; 继承是面向对象编程的三大特征之一&#xff0c;也是代码复用的手段之一。之前我们在很多的地方尝试函数的复用&#xff0c;而继承是为了类的复用提供了很好的方式。 &#xff08;1&#xff09;继承的代码怎么写 在一个类后面使用 &#xff1a;继承方…

面试经典150题——盛最多水的容器

面试经典150题 day28 题目来源我的题解方法一 双指针 题目来源 力扣每日一题&#xff1b;题序&#xff1a;11 我的题解 方法一 双指针 使用两个指针left和right&#xff0c;初始分别指向最左侧和最右侧&#xff0c;然后每次移动矮的一侧。存水量Math.min(height[left],heigh…

扩展学习|一文读懂知识图谱

一、知识图谱的技术实现流程及相关应用 文献来源&#xff1a;曹倩,赵一鸣.知识图谱的技术实现流程及相关应用[J].情报理论与实践,2015, 38(12):127-132. &#xff08;一&#xff09;知识图谱的特征及功能 知识图谱是为了适应新的网络信息环境而产生的一种语义知识组织和服务的方…

中间件研发之Springboot自定义starter

Spring Boot Starter是一种简化Spring Boot应用开发的机制&#xff0c;它可以通过引入一些预定义的依赖和配置&#xff0c;让我们快速地集成某些功能模块&#xff0c;而无需繁琐地编写代码和配置文件。Spring Boot官方提供了很多常用的Starter&#xff0c;例如spring-boot-star…

计算机系列之程序设计语言、编译原理、正规式、有限自动机

17、程序设计语言基础知识 低级语言&#xff1a;机器语言&#xff08;计算机硬件只能识别0和1的指令序列&#xff09;&#xff0c;汇编语言。 高级语言&#xff1a;功能更强&#xff0c;抽象级别更高&#xff0c;与人们使用的自然语言比较接近。 ◆汇编:将汇编语言翻译成目标…

Redis-五大数据类型-Zset(有序集合)

五大数据类型-Zset&#xff08;有序集合&#xff09; 简介 Zset与Set非常相似&#xff0c;是一个没有重复元素的String集合。 不同之处是Zset的每个元素都关联了一个分数&#xff08;score&#xff09;&#xff0c;这个分数被用来按照从低分到高分的方式排序集合中的元素。集…

RabbitMQ是怎么做消息分发的?——Java全栈知识(14)

RabbitMQ是怎么做消息分发的&#xff1f; RabbitMQ 的消息分发分为五种模式&#xff1a;分别是简单模式、工作队列模式、发布订阅模式、路由模式、主题模式。 1、简单模式 publisher 直接发送消息到队列消费者监听并处理队列中的消息 简单模式是最基本的工作模式&#xff0c;…