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

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

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

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

示例 1:

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

示例 2:

输入: root = []
输出: 0

示例 3:

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

提示:

  • 树中节点的数目范围是 [ 0 , 5 × 1 0 4 ] [0, 5 \times 10^4] [0,5×104]
  • 0 ≤ N o d e . v a l ≤ 5 ∗ 104 0 \leq Node.val \leq 5 * 104 0Node.val5104
  • 题目数据保证输入的树是 完全二叉树

进阶: 遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗?

解法一(统一迭代遍历)

思路分析:

  1. 采用统一迭代二叉树的遍历方法,来对二叉树进行遍历,在遍历的过程中统计节点数目

  2. 此处采用 前序遍历

实现代码如下:

class Solution {
    public int countNodes(TreeNode root) {
		int ans = 0;
		if (root == null)
			return ans;		// 边界条件
		Deque<TreeNode> stack = new LinkedList<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			if (node != null) {
				// 对节点进行处理 添加待遍历节点
				if (node.right != null)
					stack.push(node.right);
				if (node.left != null)
					stack.push(node.left);
				// 添加待处理节点
				stack.push(node);
				stack.push(null);	// 使用null标记待处理节点
			} else {
				stack.pop();	// 弹出待处理节点
				++ ans;		// 对节点进行计数
			}
		}
		return ans;
    }
	}
		return ans;
    }
}

提交结果如下:

解答成功:
执行耗时:9 ms,击败了5.25% 的Java用户
内存消耗:44.5 MB,击败了83.97% 的Java用户

复杂度分析:

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

解法二(BFS+队列)

思路分析:

  1. 采用层序遍历法,对二叉树进行遍历,并在遍历过程中 统计节点数

实现代码如下:

class Solution {
	// BFS
	public int countNodes(TreeNode root) {
		int ans = 0;
		if (root == null)
			return ans;		// 边界条件
		Queue<TreeNode> queue = new ArrayDeque<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; ++i) {
				++ ans;
				TreeNode node = queue.poll();
				if (node.left != null) queue.offer(node.left);
				if (node.right != null) queue.offer(node.right);
			}
		}
		return ans;
	}
}

提交结果如下:

解答成功:
执行耗时:5 ms,击败了9.04% 的Java用户
内存消耗:46.5 MB,击败了5.07% 的Java用户

复杂度分析:

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

解法三(二分查找+位运算)

思路分析:

  1. 首先题目给出该二叉树为 完全二叉树,因此可以利用完全二叉树的特性计算节点个数。

  2. 首先规定根节点位于第0层,完全二叉树的最大层数为h,且根据完全二叉树的特性有;最左边的节点一定位于最底层,且从根节点到最左边的节点的路径长度即为最大层数h

  3. 0 ≤ i < h 0 \leq i < h 0i<h时,第i层包含 2 i 2^i 2i个节点,最底层包含节点数最少为1,最多为 2 h 2^h 2h

    1. 当底层包含1个节点时,完全二叉树的节点个数是: ∑ i = 0 h − 1 2 i + 1 = 2 h \sum_{i=0}^{h-1}2^i+1 = 2^h i=0h12i+1=2h

    2. 当底层包含 2 h 2^h 2h个节点时,完全二叉树的节点个数时: ∑ i = 0 h = 2 h + 1 − 1 \sum_{i=0}^{h} = 2^{h+1} - 1 i=0h=2h+11

  4. 因此对于最大层数为h的完全二叉树,节点个数在 [ 2 h , 2 h + 1 − 1 ] [2^h, 2^{h+1}-1] [2h,2h+11]的范围内,即在该范围内通过二分查找的方式得到完全二叉树的节点个数

  5. 即根据节点个数范围的上下界得到判断的节点个数k,如果第k个节点存在,则节点个数一定大于或等于k,如果第k个节点不存在,则节点个数一定小于 k,因此每次查找的范围缩小一半,直到找到节点个数。

  6. 如何判断第k个节点是否存在?如果第k个节点位于第h层,则k的二进制表示包含h+1位,且最高位为1其余各位从高到底表示从根节点到第k个节点的路径0表示移动到左子节点,1表示移动到右子节点

  7. 通过位运算得到第k个节点对应的路径,然后判断该路径对应的节点是否存在,则可判断第k个节点是否存在

实现代码如下:

class Solution {
	// 二分查找 + 位运算
	public int countNodes(TreeNode root) {
		if (root == null) return 0;	// 边界
		// 获取二叉树的层数
		int h = 0;
		TreeNode node = root;
		while (node.left != null) {
			++ h;	// 计算二叉树的层数
			node = node.left;
		}
		// 根据二叉树的层数 获取节点数范围
		int min = 1 << h;	// 位运算计算	最低限度
		int max = (1 << (h + 1)) - 1;	// 位运算计算 最高限度
		int ans = 0;	// 即二分查找寻找符合条件的 用ans来保存
		// 二分查找区间为 左闭右闭
		while (min <= max) {
			int mid = ((max - min) >> 1) + min;
			if (exitTreeNode(mid, root, h)) {
				// 如果存在 则继续查找
				ans = mid;
				min = mid + 1;
			} else {
				max = mid - 1;
			}
		}
		return ans;		// 在结束二分查找时 min指向的节点是最后一个存在的节点
	}
	private boolean exitTreeNode(int k, TreeNode root, int level) {
		// 获取当前从根节点出发的方向
		int bits = 1 << (level-1);
		TreeNode node = root;
		while (node != null && bits > 0) {
			if ((bits & k) == 0) {
				node = node.left;
			} else {
				node = node.right;
			}
			bits >>= 1;
		}
		return node != null;
	}
}

提交结果如下:

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:46.4 MB,击败了8.84% 的Java用户

复杂度分析:

  • 时间复杂度: O ( l o g 2 n ) O(log^{2}_{}{n}) O(log2n)n为完全二叉树的节点数
  • 空间复杂度: O ( 1 ) O(1) O(1),只使用有限的额外空间

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

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

相关文章

软件测试--用例

目录 测试用例的基本要素 测试用例的设计方法--针对黑盒测试&#xff08;重要&#xff09; 等价类 边界值 错误猜测法 场景设计法 因果法 判定表法 正交表法 测试用例设计万能公式 使用工具控制网络和测试接口 控制网络&#xff08;Fiddler&#xff09; 接口测试&a…

UV胶水能够粘接聚碳酸酯PC吗?

UV胶水能够粘接聚碳酸酯PC吗&#xff1f; 聚碳酸酯PC是一种高性能工程塑料&#xff0c;透明、坚固和耐高温。常用于制造透明零件、光学设备、以及一些耐热和强度要求较高的应用&#xff0c;如&#xff1a;汽车零件、眼镜镜片、电子设备外壳等。 聚碳酸酯PC的化学性质是一种非极…

【c++】初阶模版与STL简单介绍

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;c笔记仓 朋友们大家好&#xff0c;本篇文章介绍一下模版和对STL进行简单的介绍&#xff0c;后续我们进入对STL的学习&#xff01; 目录 模版1.泛型编程2.函数模板2.1函数模板的原理2.2模版的实例化…

力扣面试150: O(1) 时间插入、删除和获取随机元素 HashMap结合数组

Problem: 380. O(1) 时间插入、删除和获取随机元素 文章目录 思路复杂度Code 思路 &#x1f469;‍&#x1f3eb; 三叶题解 复杂度 时间复杂度: O ( 1 ) O(1) O(1) 空间复杂度: O ( n ) O(n) O(n) Code class RandomizedSet {static int[] nums new int[200_010];//存…

python_3

文章目录 题目运行结果模式A模式B模式C模式D 题目 mode input("请选择模式:") n int(input("请输入数字:"))if mode "A" or mode "a":# 模式A n:输入的层数 i:当前的层数# 每行数字循环次数 ifor i in range(1, n 1):for j in r…

武汉星起航电子商务有限公司,引领跨境电商新潮流的卓越引擎

在全球经济不断演进的今天&#xff0c;跨境电商作为国际贸易的新引擎&#xff0c;正逐渐崭露头角。在这场全球商业的变革中&#xff0c;武汉星起航电子商务有限公司以其丰富的实战运营经验和专业的团队&#xff0c;成为了这个领域的佼佼者。 自2017年以来&#xff0c;武汉星起…

移动Web学习04-移动端订单结算页PC端个人中心页面

5、电商结算页面案例 css body{background-color: #F2F2F2; } * {box-sizing: border-box;margin: 0;padding: 0; }.main{padding: 12px 11px 80px; }.pay{display: flex;height: 80px;background-color: #fff;bottom: 0;width: 100%;border-top: 1px solid #ededed;position:…

某虚假交友APP(信息窃取)逆向分析

应用初探 在群里水群的时候 群u发了一个交友APP 于是拿来分析一下 可以看到应用打开后又一个登录的界面 需要用户输入手机号与验证码进行登录 #在线云沙箱分析 将APK放入某安信云沙箱中分析 提示应用请求了过多的敏感权限 逆向分析 直接拖入Jadx分析 好在程序没有加固 也没…

vulnhub靶机: DC-9

dc-9靶机下载 将靶机设置为NAT模式&#xff0c;本次实验使用的内网网段为192.168.198.0/24&#xff0c;kali的ip为192.168.198.172 信息搜集 ip主机扫描&#xff1a; nmap -sP 192.168.198.0/24 确定靶机ip为192.168.198.171 主机端口扫描&#xff1a; nmap -T4 -A -v 192…

进程并发究竟是如何进行进程切换的?Linux内核原理解析

进程并发究竟是如何进行进程切换的&#xff1f;Linux内核原理解析 一、并发二、进程切换原理三、活跃进程、过期进程3.1分时操作系统、实时操作系统3.2 运行队列queue[140]3. 3 操作系统如何查找非空进程 一、并发 在一定时间内&#xff0c;多个进程在一个CPU中采用进程切换的方…

Memcached 教程之 PHP 连接 Memcached 服务(十)

PHP 连接 Memcached 服务 在前面章节中我们已经介绍了如何安装 Memcached 服务&#xff0c;接下来我们为大家介绍 PHP 如何使用 Memcached 服务。 PHP Memcache 扩展安装 PHP Memcache 扩展包下载地址&#xff1a;PECL :: Package :: memcache&#xff0c;你可以下载最新稳定…

商业开源MES+源码+可拖拽式数据大屏

商业开源的一套超有价值的JAVA制造执行MES系统源码 带本地部署搭建教程 教你如何在本地运行运行起来。 开发环境&#xff1a;jdk11tomcatmysql8springbootmaven 需要源码&#xff0c;私信我付费获取。 一、系统概述&#xff1a; 万界星空科技免费试用MES、开源MES、商业开…

OpenGL_Learn19(混合)

OpenGL中&#xff0c;混合(Blending)通常是实现物体透明度(Transparency)的一种技术。透明就是说一个物体&#xff08;或者其中的一部分&#xff09;不是纯色(Solid Color)的&#xff0c;它的颜色是物体本身的颜色和它背后其它物体的颜色的不同强度结合。一个有色玻璃窗是一个透…

java算法day45 | 动态规划part07 ● 70. 爬楼梯 (进阶) ● 322. 零钱兑换 ● 279.完全平方数

70. 爬楼梯 &#xff08;进阶&#xff09; 题目描述&#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬至多m (1 < m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 注意&#xff1a;给定 n 是一个正整数。 输入描述&#xff1a;输入…

【JavaSE】注解

概念解释 注解与注释 注释&#xff1a;用文字描述程序的,是给程序员看的。 注解&#xff1a;用来解释说明程序的&#xff0c;是给计算机看的。 百度百科定义&#xff1a; 注解&#xff08;Annotation&#xff09;&#xff0c;也叫元数据。一种代码级别的说明。它是JDK1.5及…

FPGA常用IP核之FIFO学习

IP核是FPGA芯片公司提供的逻辑功能块&#xff0c;在FPGA芯片中可以进行优化和预先配置&#xff0c;可以直接在用户设计的程序中使用&#xff0c;应用范围很广。在FPGA设计开发过程中使用IP核&#xff0c;可以大大的缩短开发周期&#xff0c;高度优化的IP核可以使FPG开发工程师专…

8核32G云服务器幻兽帕鲁多人联机主机价格94元/月、1362元一年

8核32G云服务器京东云轻量云主机价格94元1个月、282元3个月、673元6个月、1362元一年&#xff0c;配置8C32G-100G SSD系统盘-10M带宽-2000G月流量 华北-北京&#xff0c;京东云优惠活动 yunfuwuqiba.com/go/jd 活动链接打开如下图&#xff1a; 8核32G云服务器京东云轻量云主机价…

损失函数篇 | YOLOv8更换损失函数之MPDIoU(23年7月首发论文)

前言:Hello大家好,我是小哥谈。损失函数是机器学习中用来衡量模型预测值与真实值之间差异的函数。在训练模型时,我们希望通过不断调整模型参数,使得损失函数的值最小化,从而使得模型的预测值更加接近真实值。不同的损失函数适用于不同的问题,例如均方误差损失函数适用于回…

Codeforces Round 931 (Div. 2) D1. XOR Break — Solo Version

题目 思路&#xff1a; #include <bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define lson p << 1 #define rson p << 1 | 1 const int maxn 1e6 5, inf 1e18, maxm 4e4 5; c…

机器学习综述:核心概念、方法与未来展望

一、机器学习基础 基本概念 机器学习是一门专注于开发算法来从数据中学习模式的科学。它基于这样一个假设&#xff1a;如果一个程序可以在某任务T上&#xff0c;基于经验E改善它的性能P&#xff0c;那么我们说这个程序在从经验中学习。这里的“经验”可以理解为历史数据或先前…