934. Even Odd Tree

Given the root of a binary tree, determine whether it is an Even-Odd tree. For even-indexed levels (root is level 0), all node values must be odd and strictly increasing left to right; for odd-indexed levels, all values must be even and strictly decreasing left to right. Return true or false. The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Boolean — true or false.

Examples

Input: [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: Levels satisfy the parity and monotonic rules.

Input: [5,4,2,3,3,7]
Output: false
Explanation: Level 2 is not strictly increasing.

Input: [1]
Output: true
Explanation: Single odd root.

Constraints

• 1<=nodes<=10^5
• 1<=value<=10^6

Asked by