leetcode/check-completeness-of-a-binary-tree.cpp at master · amitbansal7/leetcode · GitHub

Name: leetcode/check-completeness-of-a-binary-tree.cpp at master · amitbansal7/leetcode · GitHub
Rating: 4.4 (8321 reviews)
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
//Runtime: 4 ms - BFS
classSolution {
public:
boolisCompleteTree(TreeNode* root) {
bool null = false;

 queue<TreeNode*> q;
 q.push(root);
while (!q.empty()) {
 TreeNode* p = q.front();
 q.pop();

if (null && (p->left || p->right))
returnfalse;

if (!p->left && p->right)
returnfalse;

if (p->left) q.push(p->left); else null = true;
if (p->right) q.push(p->right); else null = true;
 }
returntrue;
 }
};

//Runtime: 4 ms
classSolution {
public:

intcount(TreeNode* root) {
if (!root) return0;
return1 + count(root->left) + count(root->right);
 }

boolcheck(TreeNode* root, int pos, int maxCount) {
if (!root) returntrue;
if (pos >= maxCount) returnfalse;
returncheck(root->left, pos * 2 + 1, maxCount) && check(root->right, pos * 2 + 2, maxCount);
 }

boolisCompleteTree(TreeNode* root) {
int maxCount = count(root);
returncheck(root, 0, maxCount);
 }
};