496. Complete Tree Check
A tournament organiser draws a bracket as a binary tree with its top node at root. The bracket is called compact if every level, except possibly the deepest one, is completely filled with nodes, and all the nodes on the deepest level sit as far to the left as possible, with no gaps between them.
Return true if the bracket is compact and false otherwise. An empty tree counts as compact. Node values are irrelevant to the answer; only the shape of the tree matters.
Example 1
- Input:
- root = [7,3,9,1,4,8]
- Output:
- true
- Explanation:
Every level except the last is full, and the last level holds 1, 4, 8 packed to the left without gaps, so the tree is compact.
Example 2
- Input:
- root = [7,3,9,1,null,8,2]
- Output:
- false
- Explanation:
Node 3 has no right child, yet node 9 on the same level has children, so there is a gap and the answer is false.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)