📃 题目描述

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

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

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

示例 1：

输入：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)