Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
解题思路：
本题求解完全二叉树的节点个数，完全二叉树的定义见wiki。最简单的方法直接递归，具体代码如下：
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == NULL) return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
递归的方法简单粗暴，代码简洁，但提交的时候直接超时了。有没有什么方法可以改进，减少计算量，我们想到满二叉树，计算完全二叉树的时候，当子树是满二叉树的时候，可以直接计算节点个数，利用公式(2^(H-1))-1，这样便可以减少递归次数。
具体代码如下：
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == NULL) return 0;
TreeNode* l = root, *r = root;
int hl = 0, hr = 0;
while(l) { hl++; l = l->left;}
while(r) { hr++; r = r->right;}
if(hl == hr) return pow(2,hl) - 1;
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
参考材料：https://discuss.leetcode.com/topic/15515/easy-short-c-recursive-solution
