Return true if every level of the binary tree follows these rules, or false otherwise. The root is at level 0, and each child is one level below its parent.
- At even-numbered levels, all values must be odd and strictly increase from left to right.
- At odd-numbered levels, all values must be even and strictly decrease from left to right.
Equal adjacent values fail the strict ordering rule. A level with one node still has to satisfy its parity rule.
Examples use level-order arrays: after the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted.
Example 1:
Input: root = [3,12,8,1,5,null,9]
Output: trueExplanation: Level 0 contains the odd value 3. Level 1 has even values [12,8] in decreasing order. Level 2 has odd values [1,5,9] in increasing order. Every level follows its rules.
Example 2:
Input: root = [3,12,8,1,1,null,9]
Output: falseExplanation: Level 2 has values [1,1,9]. Although these values are odd, the repeated 1 breaks the requirement that values strictly increase.
Example 3:
Input: root = [3,12,7]
Output: falseExplanation: Level 1 contains [12,7]. The value 7 is odd, but every value on an odd-numbered level must be even.
Constraints:
- The tree contains between 1 and 100000 nodes.
1 <= Node.val <= 1000000