1671. Heap-Shaped Check
A tournament organiser stores prize amounts in a binary tree root and wants to know whether it can be stored as a compact priority board. That requires two things at once. First, the tree must be complete: every level is entirely full except possibly the last one, and the last level has its nodes packed as far left as possible with no gaps. Second, every parent must hold a value that is greater than or equal to the value of each of its children.
Return true if both conditions hold, otherwise false. Equal values are allowed. A single node counts as valid. A single level-order pass is enough: O(n) time and O(n) space.
Example 1
- Input:
- root = [9,5,8,1,2,3]
- Output:
- true
- Explanation:
The tree is complete and every parent is at least as large as its children, so the answer is true.
Example 2
- Input:
- root = [5,3,4,null,1]
- Output:
- false
- Explanation:
The answer is false: either a gap appears before a later node or a child exceeds its parent.
Constraints
1 ≤ nodes ≤ 1000; -104 ≤ Node.val ≤ 104
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)