1609. 奇偶树

from typing import Optional


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True

        level, nodes = 0, [root]

        while len(nodes) > 0:
            next_nodes, prev = [], float('-inf') if level & 1 == 0 else float('inf')
            for node in nodes:
                if (level & 1 == 0 and node.val & 1 == 0) or (level & 1 == 1 and node.val & 1 == 1):
                    return False
                if (level & 1 == 0 and node.val <= prev) or (level & 1 == 1 and node.val >= prev):
                    return False

                prev = node.val

                if node.left is not None:
                    next_nodes.append(node.left)
                if node.right is not None:
                    next_nodes.append(node.right)

            level, nodes = level + 1, next_nodes

        return True