02、完全二叉树的节点个数

厨子大约 5 分钟数据结构算法算法基地面试二叉树层序遍历刷题程序厨校招社招

哈喽，大家好，今天给大家说一下这个题目，完全二叉树的节点个数

https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=problem-list-v2&envId=binary-treeopen in new window

题目描述

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

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

示例 1:

输入：root = [1,2,3,4,5,6]
输出：6
        1
       / \
      2   3
     / \ /
    4  5 6

示例 2:

输入：root = []
输出：0

示例 3:

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

约束条件:

树中节点的数目范围是 [0, 5 * 10^4]
0 <= Node.val <= 5 * 10^4
题目数据保证输入的树是完全二叉树

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

什么是完全二叉树？

不知道什么是完全二叉树的同学，可以看下这个文章

完全二叉树open in new window

普通遍历（O(n)）

不考虑完全二叉树的性质，直接遍历所有节点计数，可以采取之前学过的各种遍历方式

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

// 方法1: 递归遍历
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        // 当前节点 + 左子树节点数 + 右子树节点数
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

// 方法2: 迭代遍历（层序遍历）
class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        queue<TreeNode*> q;
        q.push(root);
        int count = 0;

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            count++;

            if (node->left) { 
                q.push(node->left);
            }
  
            if (node->right) {
                q.push(node->right);
            }
        }

        return count;
    }
};

时间复杂度: O(n)，需要遍历所有节点

空间复杂度: O(log n)，递归栈深度或队列大小

利用完全二叉树性质（O(log²n)）

核心思想

完全二叉树有一个重要性质：

如果左右子树高度相同 → 左子树一定是满二叉树
如果左右子树高度不同 → 右子树一定是满二叉树

情况1: 左右子树高度相同（左子树是满的）

        1              左子树高度 = 2
       / \             右子树高度 = 2
      2   3
     / \ /             左子树是满二叉树！
    4  5 6             节点数 = 左子树(2^2-1) + 右子树(递归) + 1


情况2: 左右子树高度不同（右子树是满的）

        1              左子树高度 = 2
       / \             右子树高度 = 1
      2   3
     / \               右子树是满二叉树！
    4  5               节点数 = 左子树(递归) + 右子树(2^1-1) + 1

这里需要注意哈，满二叉树的节点数，为 2^K-1

满二叉树open in new window

算法流程

暂时无法在飞书文档外展示此内容

详细图解示例

以下面这棵完全二叉树为例：

执行过程：

步骤1: countNodes(1)
  左子树高度: 从1->2->4 = 3
  右子树高度: 从1->3->6 = 3
  高度相同 → 左子树是满的
  左子树节点数 = 2^2 - 1 = 3
  继续递归右子树: countNodes(3)

步骤2: countNodes(3) // 递归右子树
  左子树高度: 从3->6 = 2
  右子树高度: 从3 = 1
  高度不同 → 右子树是满的
  右子树节点数 = 2^0 - 1 = 0
  继续递归左子树: countNodes(6)

步骤3: countNodes(6) // 继续递归
  左子树高度: 0
  右子树高度: 0
  高度相同 → 都是空，返回 1

回溯:
  countNodes(3) = 1 + countNodes(6) + 0 = 1 + 1 = 2
  countNodes(1) = 1 + 3 + countNodes(3) = 1 + 3 + 2 = 6

代码实现

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

        // 计算左右子树的高度
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);

        if (leftHeight == rightHeight) {
            // 左子树是满二叉树
            // 左子树节点数 = 2^leftHeight - 1
            // 总数 = 左子树 + 根节点 + 右子树（递归）
            return (1 << leftHeight) + countNodes(root->right);
            // (1 << leftHeight) 等价于 2^leftHeight
        } else {
            // 右子树是满二叉树
            // 右子树节点数 = 2^rightHeight - 1
            // 总数 = 右子树 + 根节点 + 左子树（递归）
            return (1 << rightHeight) + countNodes(root->left);
        }
    }

private:
    // 计算树的高度（沿着最左边的路径）
    int getHeight(TreeNode* node) {
        int height = 0;
        while (node != nullptr) {
            height++;
            node = node->left;
        }
        return height;
    }
};