BFS

LeetCode 1609 Even Odd Tree (Python)

Posted by 小明MaxMing on November 1, 2024

题目

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.

解题思路

按层进行bfs,把每层的值存在一个数组里进行判断,是否全为奇/偶数,递增/递减

代码

# 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:
        def is_increase(q, is_even):
            if is_even:
                if q[0].val % 2 == 0:
                    return False
                for i in range(1, len(q)):
                    if q[i].val % 2 == 0:
                        return False
                    if q[i].val <= q[i - 1].val:
                        return False
            else:
                if q[0].val % 2 != 0:
                    return False
                for i in range(1, len(q)):
                    if q[i].val % 2 != 0:
                        return False
                    if q[i].val >= q[i - 1].val:
                        return False
            return True

        is_even = True
        q = [root]
        while q:
            if not is_increase(q, is_even):
                return False
            tmp = []
            for n in q:
                if n.left:
                    tmp.append(n.left)
                if n.right:
                    tmp.append(n.right)
            q = tmp[:]
            is_even = not is_even
        return True

视频讲解 YouTube<--欢迎点击订阅

视频讲解 bilibili<--欢迎点击订阅