题目描述

求一棵完全二叉树的节点的个数，完全二叉树是指一棵深度为h的二叉树，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

样例

输入：一棵二叉树的根节点，二叉树如下
      1
    /   \
    2   3
   / \ / 
  4  5 6
输出：6
解释：一共6个节点

算法1

(递归) $O(logn*logn)$

二叉树一般都可以考虑成递归问题，对于每个节点，计算一直向左和一直向右的高度，如果相等则说明是满二叉树，那么该树节点个数为$2^{h}-1$(h是二叉树的高度)；如果不相等则说明不是满二叉树，则需要递归地向下求解，该棵树的节点个数等于1+左子树节点数+右子树节点数。其实这和一般的二叉树计算节点个数的思路是一样的，不同点在于这是完全二叉树，所以如果一直向左和一直向右的高度相等的话就可以马上计算出节点个数而不用继续向下递归了。
这道题相当于二分查找最后一层最后一个节点的位置，每次查找的复杂度是$O(logn)$，一共需要查找$O(logn)$次，所以复杂度为$O(logn*logn)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        int l = 0;
        int r = 0;
        TreeNode* leftp = root;
        TreeNode* rightp = root;
        while(leftp){
            l++;
            leftp = leftp->left;
        }
        while(rightp){
            r++;
            rightp = rightp->right;
        }
        if(l==r)
            return (1<<l)-1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};