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

约 5 分钟
文章信息 16 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 10-20 面试经典 150 题 腾讯 字节 阿里 微软 美团 百度 快手 B站 猿辅导
标签
树 二叉树 二分查找 位运算

题目描述

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

image-20260928221110302

image-20260928221110303

题意分析

完全二叉树只有最后一层可能没填满，而且这一层的节点从左到右连续排列。逐个访问节点需要 $O(n)$ 时间；利用这个结构，可以先识别满子树，用公式一次算出它的节点数。

解法：利用满二叉树高度剪枝

核心思路

[!blue]

高度按节点层数计算。完全二叉树的最左链一定到达最后一层，设其高度为 $h$。如果最右链也有 $h$ 层，就说明最后一层最右边的位置已有节点；这一层从左连续填充，因此所有位置都已填满，当前子树就是满二叉树。

满二叉树每层的节点数依次是 $1,2,4,\ldots,2^{h-1}$，总数为 $2^h-1$，可以直接返回，不必访问内部节点。两条边界不等高时，当前子树没有填满；它的左右子树仍是完全二叉树，可以递归计数，再加上当前根节点。

最后一层先填左子树，再填右子树。节点若已填入右子树，左子树必然已满；否则右子树少一层且已满，也可能为空。所以左右子树至多一棵不满，递归只沿这一侧继续展开，另一侧完成高度检查后便返回。

解题步骤

  1. 空节点返回 $0$。
  2. 从当前根分别沿 left、right 一直走到空节点，统计两条边界的节点层数。
  3. 两个高度相等时，用 (1 << height) - 1 计算满树节点数并返回；单节点也会在这里返回 $1$。
  4. 两个高度不等时，分别递归左右子树，返回两者之和再加 $1$。递归到满子树或空节点时停止展开。

代码实现

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

        int leftHeight = leftHeight(root);
        int rightHeight = rightHeight(root);

        // 只有在完全二叉树前提下，两条边界等高才能判定当前子树已满。
        if (leftHeight == rightHeight) {
            return (1 << leftHeight) - 1;
        }

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

    private int leftHeight(TreeNode node) {
        int height = 0;

        while (node != null) {
            height++;
            node = node.left;
        }

        return height;
    }

    private int rightHeight(TreeNode node) {
        int height = 0;

        while (node != null) {
            height++;
            node = node.right;
        }

        return height;
    }
}

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left := leftHeight(root)
    right := rightHeight(root)
    // 只有在完全二叉树前提下，两条边界等高才能判定当前子树已满。
    if left == right {
        return (1 << left) - 1
    }
    return countNodes(root.Left) + countNodes(root.Right) + 1
}

func leftHeight(node *TreeNode) int {
    height := 0
    for node != nil {
        height++
        node = node.Left
    }
    return height
}

func rightHeight(node *TreeNode) int {
    height := 0
    for node != nil {
        height++
        node = node.Right
    }
    return height
}

复杂度分析

  • 时间复杂度：$O(\log^2 n)$。设树高为 $h=O(\log n)$，每层至多一棵非满子树继续展开，连同已满的兄弟子树，高度检查的总工作量为 $O(h+(h-1)+\cdots+1)=O(h^2)$。
  • 空间复杂度：$O(\log n)$，来自递归调用栈；完全二叉树的高度为 $O(\log n)$。

关键点总结

[!green]

  • 「边界高度相等则满」依赖完全二叉树前提，不能套到任意二叉树。
  • 满子树用公式整体跳过，才真正利用了题目给出的结构性质。
  • 高度计数口径必须与公式一致：本文按节点数计高。
  • $O(\log^2 n)$ 来自「递归 $O(\log n)$ 层 × 每层计算高度 $O(\log n)$」。

易错点总结

[!yellow]

  • 把高度按边数计算，却仍使用 (1 << h) - 1，会少算一层；按边数计高时指数应为 $h+1$。
  • 只算最左链高度就套公式，无法分辨最后一层是否填满；需要同时检查最右链。
  • 非满分支忘记加当前根节点，会漏计本次递归负责的根。
  • 在普通二叉树上使用该判据：左右边界等高也可能内部缺节点，结论不成立。

相似题目

题目 难度 关联与区别
104. 二叉树的最大深度 简单 同样计算树高，本题进一步用满子树节点数公式跳过整棵子树。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/37412023
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！