Algorithm
Problem Name: 958. Check Completeness of a Binary Tree
Given the root of a binary tree, determine if it is a complete binary tree.
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 2h nodes inclusive at the last level h.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
Example 2:
Input: root = [1,2,3,4,5,null,7] Output: false Explanation: The node with value 7 isn't as far left as possible.
Constraints:
- The number of nodes in the tree is in the range
[1, 100]. 1 <= Node.val <= 1000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int d;
bool shrinked;
} dep_t;
bool verify_depth(dep_t *dep, int d) {
if (dep->d == -1) { // first time verifying a depth
dep->d = d;
return true;
}
// assert(d < = dep->d);
if (d == dep->d - 1 && !dep->shrinked) {
dep->d --;
dep->shrinked = true;
}
if (d == dep->d) {
return true;
}
return false;
}
bool traversal(struct TreeNode *node, dep_t *dep, int d) {
if (!node) {
if (!verify_depth(dep, d)) return false;
} else {
if (!traversal(node->left, dep, d + 1)) return false;
if (!traversal(node->right, dep, d + 1)) return false;
}
return true;
}
bool isCompleteTree(struct TreeNode* root) {
dep_t dep = { -1, false };
return traversal(root, &dep, 0);
}
Input
root = [1,2,3,4,5,6]
Output
true
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isCompleteTree(TreeNode root) {
Queue queue = new LinkedList<>();
queue.add(root);
boolean end = false;
while (!queue.isEmpty()) {
TreeNode removed = queue.poll();
if (removed == null) {
end = true;
} else {
if (end) {
return false;
}
queue.add(removed.left);
queue.add(removed.right);
}
}
return true;
}
}
Input
root = [1,2,3,4,5,6]
Output
true
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const isCompleteTree = function(root) {
let cur = [root]
let depth = 1
while(cur.length) {
const nxt = []
// console.log(cur)
for(let i = 0; i < cur.length; i++) {
const e = cur[i]
if(e == null) nxt.push(null, null)
else if(e) nxt.push(e.left, e.right)
}
if(!valid(cur) || (cur[cur.length - 1] == null && valid(nxt))) {
return false
}
if(nxt.some(e => e != null)) {
cur = nxt
} else {
cur = []
}
depth++
}
return true
function valid(arr) {
let firstNull = arr.length, lastNonNull = arr.length
for(let i = 0; i < arr.length; i++) {
const e = arr[i]
if(firstNull === arr.length && e == null) firstNull = i
if(e != null) lastNonNull = i
}
// console.log(firstNull, lastNonNull>
return firstNull >= lastNonNull
}
};
Input
root = [1,2,3,4,5,null,7]
Output
false
#4 Code Example with C# Programming
Code -
C# Programming
class Solution:
def isCompleteTree(self, root):
q, pre = [root, None], 1
while any(q):
i = q.index(None)
if any(q[i:]) or pre > 1:
return False
pre = len(q[i:])
q = [child for node in q[:i] for child in (node.left, node.right)] + [None]
return True
Input
root = [1,2,3,4,5,null,7]
Output
false