538. Odd-Even Floors
A building plan is stored as a binary tree root whose floors are its levels, numbered from 1 at the root. Every node holds a positive integer. The plan is valid when both of these rules hold. On every odd-numbered floor (1, 3, 5, ...) all values are even and, read from left to right, never decrease (equal neighbours are fine). On every even-numbered floor (2, 4, 6, ...) all values are odd and, read from left to right, never increase. Return true if the plan is valid and false otherwise. An empty tree is considered valid.
Example 1
- Input:
- root = [6,9,7,2,2,4,8]
- Output:
- true
- Explanation:
Floor 1 is [6] (even), floor 2 is [9, 7] (odd, non-increasing) and floor 3 is [2, 2, 4, 8] (even, non-decreasing).
Example 2
- Input:
- root = [4,3,5]
- Output:
- false
- Explanation:
Floor 2 reads [3, 5], which increases although even floors must not increase.
Example 3
- Input:
- root = [8,5,5,6,6,null,2]
- Output:
- false
- Explanation:
Floor 3 reads [6, 6, 2] left to right, which decreases on an odd floor.
Constraints
0 ≤ number of nodes ≤ 500
1 ≤ Node.val ≤ 106
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(w)