## 题目描述：

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 2^h nodes inclusive at the last level h.

## 解题思路：

### 解法I：二分枚举

```Lv0        1
/    \
Lv1     2      3
/  \   /  \
Lv2   4   5  6   -

No.   00  01 10```

## 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) {
int depth = 0;
TreeNode* node = root;
while (node) {
depth++;
node = node->left;
}
if (depth == 0) {
return 0;
}
int left = 0, right = (1 << (depth - 1)) - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (getNode(root, mid, depth - 1)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return (1 << (depth - 1)) + right;
}
TreeNode* getNode(TreeNode* root, int path, int depth) {
while (depth-- && root) {
if (path & (1 << depth)) {
root = root->right;
} else {
root = root->left;
}
}
return root;
}
};
``````

## 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 hl = 0, hr = 0;
TreeNode *l = root, *r = root;
while(l) {hl++; l = l->left;}
while(r) {hr++; r = r->right;}
if (hl == hr) return pow(2, hl) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
``````

Pingbacks已关闭。

1. King 发布于 2015年6月9日 14:09 #

第一种方法如果 h > 32 还能得出正确结果吗？

2. 在线疯狂 发布于 2015年6月9日 15:38 #

对于Python来说可以，Python的long类型可以支持非常大的数

3. Roman终将成为威尼斯人 发布于 2015年6月11日 08:52 #

第二种方法leetcode不能accept，Last executed input: Special Judge: very large tree

4. 在线疯狂 发布于 2015年6月11日 09:29 #

刚才试了一下，可以通过，你指的是C++代码吗？

5. Roman终将成为威尼斯人 发布于 2015年6月18日 05:25 #

额，我没说清楚。我用的java，最慢的～

6. xiaolittle 发布于 2015年7月18日 10:47 #

为什么left = (1 << (dep - 2)) - 1就不行呢？感觉只需要算最后一层就好了啊？