奇偶树

标签: 树 广度优先搜索 二叉树

难度: Medium

如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：

  • 二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
  • 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
  • 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减

给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

 

示例 1：

输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，因此这是一棵奇偶树。

示例 2：

输入：root = [5,4,2,3,3,7]
输出：false
解释：每一层的节点值分别是：
0 层：[5]
1 层：[4,2]
2 层：[3,3,7]
2 层上的节点值不满足严格递增的条件，所以这不是一棵奇偶树。

示例 3：

输入：root = [5,9,1,3,5,7]
输出：false
解释：1 层上的节点值应为偶数。

示例 4：

输入：root = [1]
输出：true

示例 5：

输入：root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
输出：true

 

提示：

  • 树中节点数在范围 [1, 105] 内
  • 1 <= Node.val <= 106

Submission

运行时间: 190 ms

内存: 0.0 MB

# 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:
        queue = deque()
        queue.append(root)
        isEvenLevel = True

        while queue:
            prevVal = 0 if isEvenLevel else float('inf')
            for _ in range(len(queue)):
                curr = queue.popleft()
                currVal = curr.val

                if isEvenLevel:
                    isValid = (prevVal < currVal and currVal % 2 == 1)
                else:
                    isValid = (prevVal > currVal and currVal % 2 == 0)

                if not isValid:
                    return False

                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)

                prevVal = currVal
        
            # Reset
            isEvenLevel = not isEvenLevel
        
        return True

Explain

该解法使用宽度优先搜索（BFS）来遍历二叉树的各层。使用一个队列来存储当前层的所有节点，并使用一个布尔变量 `isEvenLevel` 来标记当前层是否是偶数层。对于每层，我们使用一个变量 `prevVal` 来记录前一个节点的值以便进行比较。对于偶数层，所有节点的值应为奇数且严格递增；对于奇数层，所有节点的值应为偶数且严格递减。如果任何节点不符合这些条件，函数立即返回 `false`。如果成功遍历完整棵树，则返回 `true`。

时间复杂度: O(n)

空间复杂度: O(n)

# 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:
        queue = deque()
        queue.append(root)
        isEvenLevel = True

        while queue:
            prevVal = 0 if isEvenLevel else float('inf')
            for _ in range(len(queue)):
                curr = queue.popleft()
                currVal = curr.val

                if isEvenLevel:
                    isValid = (prevVal < currVal and currVal % 2 == 1)
                else:
                    isValid = (prevVal > currVal and currVal % 2 == 0)

                if not isValid:
                    return False

                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)

                prevVal = currVal
        
            # Toggle the level indicator
            isEvenLevel = not isEvenLevel
        
        return True

Explore

在算法中，通过使用队列（queue）存储每一层的节点，并在遍历当前层的每个节点时，使用变量`prevVal`来记录当前层前一个节点的值。对于偶数层，检查当前节点值（`currVal`）是否比`prevVal`大并且是奇数；对于奇数层，检查当前节点值是否比`prevVal`小并且是偶数。这种方式确保了每一层的节点值都按照题目要求的递增或递减顺序进行比较和验证。

在偶数层，所有节点的值必须是奇数并且比前一个节点的值大，所以使用`prevVal < currVal`来确保值是递增的；在奇数层，所有节点的值必须是偶数并且比前一个节点的值小，所以使用`prevVal > currVal`来确保值是递减的。这些条件帮助确保每个节点的值不仅符合其奇偶性要求，还符合所在层级的顺序要求。

这是因为题目特定地要求每一层的节点不仅遵守严格的递增或递减顺序，还要求节点值满足特定的奇偶性：偶数层的节点值必须是奇数，奇数层的节点值必须是偶数。因此，在遍历时，同时检查节点值的奇偶性和它们的递增或递减顺序，可以确保所有条件同时满足，从而验证树是否为一个有效的奇偶树。

初始化`prevVal`为`0`或`float('inf')`是因为它们分别为偶数层和奇数层设定了一个起始比较值。对于偶数层，节点值需要是严格递增的奇数，因此从`0`（一个偶数）开始比较可以确保第一个节点值（必须是奇数）总是有效的。对于奇数层，由于节点值需要是严格递减的偶数，因此从无限大（`float('inf')`）开始可以确保第一个节点值（必须是偶数）总是有效的。这种方式是确保每层首个节点值检查的正确性，以及后续节点值能正确按照题目要求递增或递减。