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

Categories:

Tags:

题目描述
思路分析
1. 解法一：利用完全二叉树性质（推荐）
2. 解法二：二分查找 + 位运算
相似题目

题目描述

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

思路分析

解法一：利用完全二叉树性质（推荐）

核心思路：

完全二叉树除最后一层外，其余层全部填满；最后一层的节点从左到右连续排列。

对任意子树，分别计算其最左侧深度 leftDepth 和最右侧最左侧深度 rightDepth：

若 leftDepth == rightDepth，说明该子树是满二叉树，节点数直接为 2^leftDepth - 1。

若 leftDepth != rightDepth，说明最后一层的节点尚未填满，递归计算左右子树的节点数再加 1（根节点）。

由于每次递归都有一侧子树是满二叉树（可以 O(1) 计算），递归深度为 O(log n)，每层计算深度需 O(log n)，总时间复杂度为 O(log²n)。

复杂度分析：

时间复杂度：O(log²n)，其中 n 表示完全二叉树的节点总数；每次递归深度 O(log n)，计算子树高度需 O(log n)

空间复杂度：O(log n)，其中 log n 表示递归调用栈的深度

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

        // 计算左子树最左侧深度
        int leftDepth = 0;
        TreeNode left = root;
        while (left != null) {
            leftDepth++;
            left = left.left;
        }

        // 计算右子树最左侧深度
        int rightDepth = 0;
        TreeNode right = root;
        while (right != null) {
            rightDepth++;
            right = right.right;
        }

        // 左右深度相等，说明是满二叉树，节点数为 2^depth - 1
        if (leftDepth == rightDepth) {
            return (1 << leftDepth) - 1;
        }

        // 否则递归计算左右子树节点数，再加上根节点
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

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

    // 计算左子树最左侧深度
    leftDepth := 0
    left := root
    for left != nil {
        leftDepth++
        left = left.Left
    }

    // 计算右子树最左侧深度
    rightDepth := 0
    right := root
    for right != nil {
        rightDepth++
        right = right.Right
    }

    // 左右深度相等，说明是满二叉树，节点数为 2^depth - 1
    if leftDepth == rightDepth {
        return (1 << leftDepth) - 1
    }

    // 否则递归计算左右子树节点数，再加上根节点
    return countNodes(root.Left) + countNodes(root.Right) + 1
}

解法二：二分查找 + 位运算

核心思路：

完全二叉树的节点数范围为 [2^(h-1), 2^h - 1]，其中 h 为树的高度。

对最后一层的节点编号进行二分查找（编号从 1 到 2^(h-1)），判断某编号节点是否存在。

用位运算沿路径向下查找：编号的二进制位（从高到低，跳过最高位）表示在每一层向左（0）或向右（1）走。

二分查找次数为 O(log n)，每次判断路径长度为 O(log n)，总时间复杂度 O(log²n)。

复杂度分析：

时间复杂度：O(log²n)，其中 n 表示完全二叉树的节点总数

空间复杂度：O(1)，仅使用常量级额外空间

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;
        }

        // 最后一层节点编号范围 [1, 2^h]，二分查找最后存在的节点
        int lo = 1, hi = 1 << h;
        while (lo < hi) {
            // 取右中位数，避免死循环
            int mid = lo + (hi - lo + 1) / 2;
            if (exists(root, h, mid)) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }

        // 前 h 层满节点数 + 最后一层存在的节点数
        return (1 << h) - 1 + lo;
    }

    // 判断第 h 层编号为 k 的节点是否存在
    private boolean exists(TreeNode root, int h, int k) {
        int lo = 1, hi = 1 << h;
        TreeNode node = root;
        // 从根向下走 h 步
        for (int i = 0; i < h; i++) {
            int mid = lo + (hi - lo) / 2;
            if (k <= mid) {
                node = node.left;
                hi = mid;
            } else {
                node = node.right;
                lo = mid + 1;
            }
        }
        return node != null;
    }
}

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

    // 计算树的高度（最左路径长度，不含根节点层）
    h := 0
    node := root
    for node.Left != nil {
        h++
        node = node.Left
    }

    // 最后一层节点编号范围 [1, 2^h]，二分查找最后存在的节点
    lo, hi := 1, 1<<h
    for lo < hi {
        // 取右中位数，避免死循环
        mid := lo + (hi-lo+1)/2
        if exists(root, h, mid) {
            lo = mid
        } else {
            hi = mid - 1
        }
    }

    // 前 h 层满节点数 + 最后一层存在的节点数
    return (1<<h) - 1 + lo
}

// exists 判断第 h 层编号为 k 的节点是否存在
func exists(root *TreeNode, h, k int) bool {
    lo, hi := 1, 1<<h
    node := root
    // 从根向下走 h 步
    for i := 0; i < h; i++ {
        mid := lo + (hi-lo)/2
        if k <= mid {
            node = node.Left
            hi = mid
        } else {
            node = node.Right
            lo = mid + 1
        }
    }
    return node != nil
}

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	二叉树 / DFS / BFS
111. 二叉树的最小深度	简单	二叉树 / BFS
958. 二叉树的完全性检验	中等	完全二叉树 / BFS
102. 二叉树的层序遍历	中等	二叉树 / BFS
662. 二叉树最大宽度	中等	二叉树 / BFS / 编号
297. 二叉树的序列化与反序列化	困难	二叉树 / BFS / 序列化
530. 二叉搜索树的最小绝对差	简单	二叉搜索树 / 中序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/37412023