15_完全二叉树的节点个数

简介: 15_完全二叉树的节点个数

完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 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
  • 题目数据保证输入的树是 完全二叉树

法一:递归法

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

int getNodesNum(TreeNode root)

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

if (cur == null)  return 0;

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

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

时间复杂度:O(n)

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

class Solution {
  //通用递归解法
  public int countNodes(TreeNode root) {
    if (root == null) {
      return 0;
    }
    return 1 + countNode(root.left) + countNode(root.right);
  }
}

法二:迭代法

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)  return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int count = 1;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            while (levelSize-- > 0) {
                TreeNode temp = queue.poll();
                if (temp.left != null) {
                    queue.add(temp.left);
                    count++;
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                    count++;
                }
            }
        }
        return count;
    }
}

法三:完全二叉树的特性

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

class Solution {
  /
        针对完全二叉树的解法,满二叉树的节点数为:2^depth - 1
    */
    public int countNodes(TreeNode root) {
        if (root == null)  return 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0, rightDepth = 0;//这里初始化为0是有目的的,为了下面求指数方便
        while (left != null) {  //求左子树的深度
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            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;
    }
}
相关文章
|
NoSQL Java Redis
Spring boot整合Redis实现发布订阅(超详细)
Redis发布订阅(pub/sub)是一种消息通信模式:发送者(pub)发送消息,订阅者(sub)接收信息。微信,微博,关注系统 Redis客户端可以订阅任意数量的频道
10114 0
Spring boot整合Redis实现发布订阅(超详细)
|
8月前
|
算法
动态规划之完全背包
本文详解完全背包问题:作为动态规划经典题型,区别于01背包(每物限选1次),其特点是每种物品可无限次选取。文章从定义、状态转移方程(dp[i][j] = max(dp[i-1][j], dp[i][j-w]+v))、二维/一维实现到遍历顺序对组合数与排列数的影响,结合零钱兑换II、组合总和IV等5道典型例题深入剖析,助力掌握核心思想与编码技巧。
399 1
|
3月前
|
存储 关系型数据库 MySQL
大模型推理成本优化实战:vLLM 与 KV Cache 调优指南
大模型落地后,真正制约成本的常非模型本身,而是每生成1个Token的开销。长上下文与高并发下,KV Cache迅速吞噬显存,成为性能瓶颈。vLLM通过PagedAttention、Continuous Batching、Prefix Caching等系统性优化,显著提升GPU利用率与吞吐,降低单位Token成本。
617 0
大模型推理成本优化实战:vLLM 与 KV Cache 调优指南
|
4月前
|
运维 Cloud Native 物联网
基于阿里云IoT搭建企业固定资产全生命周期管理系统落地实践
本文介绍基于阿里云IoT、RFID与云原生技术构建的轻量化固定资产管理系统,实现入库、领用、调拨、运维到报废的全生命周期闭环管理,解决账实不符、盘点低效、权责不清等痛点,提升资产可视化、可溯化、合规化管理水平。(239字)
|
3月前
|
人工智能 数据可视化 数据挖掘
Quick BI AIPro 全新发布,让数据成为企业增长引擎!
阿里云Quick BI AIPro正式发布!AI-native架构全新升级,支持自然语言对话分析,5大能力进化:深度分析、业务理解、行动推动、可信追溯、组织协同。首月赠12.5万Credits,0成本快速上手,存量客户无缝升级,新用户上传数据即用。立即免费试用!
504 0
|
6月前
|
弹性计算 人工智能 测试技术
2026年阿里云便宜云服务器推荐与选购指南
2026年阿里云推出史上最强优惠:打破新老用户壁垒,实现“新老同价、续费同价”。99元/年e实例、199元/年u1实例长期稳定;新用户可抢38元/年轻量服务器;企业享百万迁云补贴与GPU 4折。省钱避坑指南,助你轻松上云!
980 4
|
7月前
|
编解码 自然语言处理 安全
无接口也能通:实在Agent如何用ISSUT屏幕语义技术打通企业异构系统孤岛
实在Agent首创ISSUT屏幕语义理解技术,不依赖API,像人一样“看懂”并操作各类系统界面(SAP/钉钉/网银/老旧OA等),自动完成跨系统数据搬运与流程闭环,破解企业“系统孤岛”难题,开箱即用,安全合规。(239字)
|
安全 算法 网络安全
一张图就把HTTPS工作原理讲明白了!
【10月更文挑战第31天】
7772 1
一张图就把HTTPS工作原理讲明白了!
|
机器学习/深度学习 数据采集 人工智能
设计文档:智能化医疗设备数据分析与预测维护系统
本系统的目标是构建一个基于人工智能的智能化医疗设备的数据分析及预测维护平台,实现对医疗设备运行数据的实时监控、高效处理和分析,提前发现潜在问题并进行预防性维修,从而降低故障率,提升医疗服务质量。
|
算法 搜索推荐 Shell