Keshawn_lu's Blog

Leetcode 222. 完全二叉树的节点个数

字数统计: 298阅读时长: 1 min
2020/11/24 Share

题目简介:

给出一个完全二叉树,求出该树的节点个数。

说明:

完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 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
/**
* 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 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;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: