diff options
Diffstat (limited to 'check_complete_bt.cpp')
-rw-r--r-- | check_complete_bt.cpp | 26 |
1 files changed, 26 insertions, 0 deletions
diff --git a/check_complete_bt.cpp b/check_complete_bt.cpp new file mode 100644 index 0000000..4054423 --- /dev/null +++ b/check_complete_bt.cpp @@ -0,0 +1,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(); + } +}; |