LeetCode 1609 solution

problem

A binary tree is named Even-Odd if it meets the following conditions:

- The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
- For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
- For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]

Output: true

Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]

Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

python

# 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
from collections import deque
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False
        queue = deque([(root,0)]) # node, level
        while queue:
            prev = None
            for _ in range(len(queue)):
                node, level = queue.popleft()
                if level%2 == 0 and (node.val%2==0 or (prev is not None and prev >= node.val)):
                    return False
                if level%2 == 1 and (node.val%2==1 or (prev is not None and prev <= node.val)):
                    return False
                prev = node.val
                if node.left :
                    queue.append((node.left, level + 1))
                if node.right : 
                    queue.append((node.right, level + 1))
        return True

저번 문제보다 조금 더 나아가야한다. level에 대해서 규정하고, 두 조건을 만족하지 못하는 경우 바로 False return을 하고, 끝까지 나아가면 True return을 한다.