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.
解題思路：
本題求解完全二叉樹的節(jié)點(diǎn)個數(shù)飒赃，完全二叉樹的定義見wiki惰许。最簡單的方法直接遞歸蛀缝，具體代碼如下：
class Solution {
public:
int countNodes(TreeNode* root) {
if(root == NULL) return 0;
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
遞歸的方法簡單粗暴丑掺，代碼簡潔棠涮，但提交的時候直接超時了。有沒有什么方法可以改進(jìn)，減少計(jì)算量，我們想到滿二叉樹授段，計(jì)算完全二叉樹的時候，當(dāng)子樹是滿二叉樹的時候番甩，可以直接計(jì)算節(jié)點(diǎn)個數(shù)侵贵，利用公式(2^(H-1))-1，這樣便可以減少遞歸次數(shù)缘薛。
具體代碼如下：
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
