给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
● 进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

解题思路：寻找满二叉树

(1) 最简单的思路，就是将其当作一颗普通的二叉树，进行遍历。实现的方法：递归、迭代(dfs)、迭代(层次)。

(2) 利用完全二叉树的性质。⭐
我们知道一颗满二叉树的节点数量是可以通过公式求得：2^h - 1。如果我们在计算左子树、右子树的节点数量时，已知当前子树是满二叉树，就可以利用公式帮助我们大大缩短递归时间。

示例1

⭕ 问题是：我们如何知道当前子树是满二叉树？——借助于完全二叉树的性质！
我们知道完全二叉树除了最后一层之外，上面的所有节点都是满的，而且最后一层的节点集中在左侧。
因此，只要当前子树，向左递归的深度 == 向右递归的深度，那么这棵树就是满二叉树。

示例2

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        return count(root);
    }
    public int count(TreeNode node){
        if(node == null) return 0;

        // 优化：判断当前节点下的子树是否为满二叉树
        int leftEdgeDepth = edgeDeption(node, true);
        int rightEdgeDepth = edgeDeption(node, false);
        if(leftEdgeDepth == rightEdgeDepth) return (int)Math.pow(2, leftEdgeDepth) - 1;

        int leftCount = count(node.left);
        int rightCount = count(node.right);
        return 1 + leftCount + rightCount;
    }
    public int edgeDeption(TreeNode node, boolean isLeft){
        int depth = 0;
        if(isLeft){
            while(node != null){
                depth++;
                node = node.left;
            }
        }else{
             while(node != null){
                depth++;
                node = node.right;
            }
        }
        return depth;
    }
}

(3) 使用二分查找 + 位运算
官方题解完全二叉树的节点个数 - 力扣（LeetCode）