aboutsummaryrefslogtreecommitdiff
path: root/check_complete_bt.cpp
blob: 4054423e30f35313ef9722edbbf80e4c9a9a6549 (plain)
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
// 958. Check Completeness of a Binary Tree
#include "leetcode.h"

/*
 * given 'root' of binary tree, determine if it is a complete binary tree. in a
 * completely filled 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.
 */

class Solution {
public:
  bool isCompleteTree(TreeNode *root) {
    vector<TreeNode *> bfs;
    bfs.push_back(root);
    int i = 0;
    while (i < bfs.size() && bfs[i]) {
      bfs.push_back(bfs[i]->left);
      bfs.push_back(bfs[i]->right);
      i++;
    }
    while (i < bfs.size() && !bfs[i])
      i++;
    return i == bfs.size();
  }
};