NeetCode #437LC-958MediumTrees
← Back to All Problems#437 · #958 · Check Completeness of a Binary Tree(二叉树的完全性检验)
📌 Problem Statement & Constraints
Given the root of a binary tree, determine whether it is a complete binary tree: every level except possibly the last is full, and all nodes on the last level are as far left as possible. Constraints: the number of nodes is in
[1, 100].💡 Core Algorithmic Approaches
- A complete tree, read in level order, has no node after the first
None. - So do a BFS that also enqueues
Nonechildren, and stop accepting nodes once aNonehas been seen. - If any real node appears after a
None, the tree is not complete. - This is the simplest and most robust check.
💻 Benchmark Python3 Implementation
class Solution:
def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
from collections import deque
q = deque([root])
seen_null = False
while q:
node = q.popleft()
if not node:
seen_null = True # the first gap
continue
if seen_null:
return False # a node after a gap -> incomplete
# enqueue children including None, so gaps are visible
q.append(node.left)
q.append(node.right)
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node (and null slot) is dequeued once.
💾 Space Complexity
O(w) for the widest level.
⚠️ Interview Pitfalls & Follow-ups
- Skipping
Nonechildren when enqueuing: the gaps would be invisible and every tree would look complete. - Returning
Truewhen the queue empties withseen_nullset: that is the correct outcome -- the check is for nodes *after* the gap. - Counting nodes and comparing with the expected complete-tree size: it works but requires the height and is more code.
- Assuming the tree is balanced: completeness is a different property.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.