思路：

最简单的办法莫过于遍历所有的结点，统计个数，但是不管是哪种遍历，时间复杂度都要求至少为O(n)，因为要遍历每一个结点。 方法一：遍历法 不符合复杂度要求！！！ 方法二：二分法（利用性质） 由此，我们可以从完全二叉树的性质下手：

完全二叉树叶子结点只能出现在最下两层
最下层的叶子一定集中在左部连续位置，因此最深处一定在最左下角（可用来求子树深度）
如果倒数第二层出现叶子，则一定在右边且连续因此对于一棵二叉树的两个子树，若是深度相同，则左边子树一定满的，若是左边比较高，则右边子树一定是满的。（满二叉树：二叉树每一层都是满节点） 而满二叉树的结点公式为2^n-1

class Solution {
public:
    int treeLevel(struct TreeNode* head) { //因满二叉树左边先排满，所以最大深度一定在左下角
        int level = 0;
        while(head){  //计算左子树最大深度
            level++;
            head = head->left;
        }
        return level;
    }
    int nodeNum(struct TreeNode* head) {
        if(head == NULL) //空树无结点
            return 0;
        int count = 0;
        int left = treeLevel(head->left);//分别计算左右子树的最大深度
        int right = treeLevel(head->right);
        if (left == right){
            // 那么左子树为满二叉树
            //(根节点) + (1 << leftH)-1(左完全左子树节点数2^n-1) + 右子树节点数量
            count += 1 + (1 << left) - 1;
            count += nodeNum(head->right);
        }else {
            // 那么右子树为满二叉树
            count += 1 + (1 << right) - 1 ;
            count += nodeNum(head->left);
        }
        return count;
    }
};

复杂度分析：

时间复杂度：O((lgn)^2)，每次到最左寻找最大深度时间为树的最大深度O(lgn)，对于不满的二叉树递归下去，递归也是O(lgn)，相乘即为O((lgn)^2)
空间复杂度：O(lgn)，递归栈最大深度

题解 | #完全二叉树结点数#

思路：