题目简介：
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ $2^h$个节点。
示例:
1
2
3
4
5
6
7
8
| 输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
|
思路：
广度优先搜索，若当前层数的结点数不等于$2^{h-1}$，则说明这层为最后一层，直接返回size + res即可。
否则，遍历每层的结点，将其加入队列中。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
class Solution {
public:
int countNodes(TreeNode* root) {
if(!root)
return 0;
int res = 0;
queue<TreeNode*> qu;
qu.push(root);
int level = 0;
while(!qu.empty()){
int size = qu.size();
if(size != pow(2, level))
return size + res;
res += size;
for(int i = 0; i < size; i++){
TreeNode* node = qu.front();
qu.pop();
if(node -> left)
qu.push(node -> left);
if(node -> right)
qu.push(node -> right);
}
level++;
}
return res;
}
};
|
