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

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

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

示例 1：

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

示例 2：

输入：root = []
输出：0

示例 3：

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

提示：

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

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

二分，利用高度计算总数

有返回值无信息参数的DFS

计算子树的高度，根据子树的高度和完全二叉树的性质计算个数。

class Solution {
    // 计算二叉树节点的总数
    public int countNodes(TreeNode root) {
        // 如果根节点为空，则返回0
        if (root == null) {
            return 0;
        }
        
        // 计算左子树的最大深度
        int left = countLevel(root.left);
        // 计算右子树的最大深度
        int right = countLevel(root.right);

        // 如果左子树和右子树的最大深度相同，说明左子树是满的
        if (left == right) {
            // 右子树的节点总数 + (1 << left) 表示左子树加上根节点的节点总数。注意，左子树的节点总数是(1<<left)-1
            return countNodes(root.right) + (1 << left);
        } else {
            // 如果左子树和右子树的深度不同，说明右子树是满的
            // 左子树的节点总数 + (1 << right) 表示右子树加上根节点的节点总数
            return countNodes(root.left) + (1 << right);
        }
    }

    // 迭代计算从根节点到最左节点的深度
    private int countLevel(TreeNode root) {
        int level = 0;
        
        // 遍历左子树直到叶子节点，计算深度
        while (root != null) {
            level++;
            // 一定要往左走，因为完全二叉树是先填左边再填右边。所以往左走得到的深度才是最大深度。重点。
            root = root.left;
        }
        
        return level;
    }
}

1. 计算树的深度 countLevel 函数：

   • 计算从根节点到最左节点的深度，这个操作只需要沿着树的一条路径遍历到最底层。
   • 对于完全二叉树，高度为 log(n)（n 是节点数）。
   • 所以 countLevel 函数的时间复杂度为 O(log(n))。

2. 计算节点总数 countNodes 函数：

   • 每次递归调用中，计算左右子树的深度（countLevel）。
   • 每次递归将树高度减少1层，总共会递归 log(n) 次。
   • 每次递归中，计算左右子树的深度时间复杂度为 O(log(n))。
   • 所以，计算节点总数的时间复杂度为 O(log(n) * log(n))。

综上所述，时间复杂度为 O((log(n))^2)。

1. 递归栈空间：

   • 递归的深度为树的高度，对于完全二叉树，高度为 log(n)。
   • 每次递归调用都会占用栈空间。
   • 所以，空间复杂度为 O(log(n))。

2. 辅助存储空间：

   • countLevel 函数计算深度时不需要额外空间。
   • 整个过程中的额外空间使用主要是递归栈空间。

综上所述，空间复杂度为 O(log(n))。