Problem
Given a binary tree, determine if it is a complete binary tree.
Definition of a complete binary tree from Wikipedia:In a complete 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.
Solution
class Solution {
public boolean isCompleteTree(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean lastLevel = false;
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur == null) lastLevel = true;
else {
if (lastLevel) return false;
queue.offer(cur.left);
queue.offer(cur.right);
}
}
return true;
}
}