aboutsummaryrefslogtreecommitdiff
path: root/even_odd_tree.py
blob: 202fcf55014e31cfcd3107c19d1f567d3156ccd7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 1609. Even Odd Tree
import collections

"""
a binary tree is even-odd if it meets the following conditions. the root of
the binary tree is at level index 0 it s children are at level index 1 and
their children are at level index 2, etc. for every even indexed level, all
nodes at the level have odd integer values in strictly ordere (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 'root' of a
binary tree, return true if the binary tree is even-odd, otherwise return
false.
"""


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


class Solution(object):
    def isEvenOddTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        queue = collections.deque([root])
        is_even = True
        while queue:
            prev = None
            for _ in range(len(queue)):
                node = queue.popleft()
                if is_even:
                    if node.val % 2 == 0:
                        return False
                    if prev and prev.val >= node.val:
                        return False
                else:
                    if node.val % 2 == 1:
                        return False
                    if prev and prev.val <= node.val:
                        return False
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                prev = node
            is_even = not is_even
        return True