CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

    • 二叉树理论基础
    • 二叉树的四种遍历方法
    • 如何构造一棵二叉树
    • 序列化与反序列化二叉树
    • 左叶子之和
    • 找树左下角的值
    • 二叉树每层的最大值
    • 二叉树的右侧视图
    • 二叉树的锯齿形层序遍历
    • 翻转二叉树
    • 合并二叉树
    • 二叉树剪枝
    • 对称二叉树
    • 另一棵树的子树
    • 剑指 Offer 26 - 树的子结构
    • 寻找重复的子树
    • 二叉树的最大深度
    • 二叉树的最小深度
    • 二叉树的最大宽度
    • 完全二叉树的节点个数
      • 📃 题目描述
      • 🔔 解题思路
        • 迭代法
        • 递归法
        • 利用完全二叉树的性质
      • 💥 复杂度分析
    • 往完全二叉树添加节点
    • 二叉树的完全性检验
    • 平衡二叉树
    • 二叉树的最近公共祖先
    • 最大二叉树
    • 从中序与后序遍历序列构造二叉树
    • 从前序与中序遍历序列构造二叉树
    • 节点之和最大的路径
    • 二叉树的直径
    • 二叉搜索树

    • TreeSet 和 TreeMap

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 二叉树
小牛肉
2021-11-17
目录

完全二叉树的节点个数

# 📃 题目描述

题目链接:222. 完全二叉树的节点个数 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)

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

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

示例 1:

img

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

示例 2:

输入:root = []
输出:0

示例 3:

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

# 🔔 解题思路

# 迭代法

最简单最容易想到,就是直接迭代遍历一遍这个二叉树,在遍历过程中记录节点的数量就可以了,这里给出层序遍历的解法:

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 二叉树节点个数
        int res = 0;

        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                TreeNode cur = queue.poll();
                res ++;

                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }

        return res;
    }
}

# 递归法

用递归来做也可以,参考上一题 104. 二叉树的最大深度 - 力扣(LeetCode) (leetcode-cn.com) (opens new window),用递归后序遍历,先递归获取左子树的节点个数,再递归获取右子树的节点个数,然后两者相加再加 1,就是整个二叉树的节点个数

class Solution {
    public int countNodes(TreeNode root) {
        // 递归出口
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }

        int leftSize = countNodes(root.left);
        int rightSize = countNodes(root.right);

        return leftSize + rightSize + 1;
    }
}

# 利用完全二叉树的性质

不过呢,我们上面两种方法,具有普适性,并没有利用好完全二叉树的性质。

完全二叉树只有两种情况

  • 情况一:就是满二叉树
  • 情况二:最后一层叶子节点没有满

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

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

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        TreeNode left = root.left;
        TreeNode right = root.right;

        int leftHeight = 0;
        int rightHeight = 0;

        while (left != null) {
            left = left.left;
            leftHeight ++;
        }
        while (right != null) {
            // 注意这里,对于满二叉树/完全来说,非叶子节点的左子树总是不为空的
            // 所以如果想要通过左右子树的高度来判断是否是满二叉树,对于右子树来说,必须遍历其右孩子而不是左孩子
            right = right.right;
            rightHeight ++;
        }

        if (leftHeight == rightHeight) {
            // 2 << leftHieght = 2 * (2 ^ leftHeight) = 2 ^ (leftHeight + 1) - 1
            // 整棵树的高度是 leftHeight + 1
            return (2 << leftHeight) - 1;
        }

        return countNodes(root.left) + countNodes(root.right) + 1;
    }
    
}

如果对位运算不熟悉的话,可以改成下面这样:

# 💥 复杂度分析

  • 空间复杂度:三种方法的空间复杂度都是 O(LogN)
  • 时间复杂度:递归和迭代法的时间复杂度 O(N),利用完全二叉树的性质的解法其时间复杂度是 O(LogN * LogN)

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
二叉树的最大宽度
往完全二叉树添加节点

← 二叉树的最大宽度 往完全二叉树添加节点→

最近更新
01
我掏出这个多线程轮子,面试官直接全体起立
04-13
02
面试官问你有其他 Offer 吗,该怎样回答
04-10
03
天不生陈志龙,职场万古如长夜
04-06
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式