LeetCode 题解工作台
奇偶树
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ： 二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减 …
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
BFS 逐层遍历，每层按照奇偶性判断，每层的节点值都是偶数或奇数，且严格递增或递减。 时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
- 二叉树根节点所在层下标为
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
解题思路
方法一：BFS
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:
even = 1
q = deque([root])
while q:
prev = 0 if even else inf
for _ in range(len(q)):
root = q.popleft()
if even and (root.val % 2 == 0 or prev >= root.val):
return False
if not even and (root.val % 2 == 1 or prev <= root.val):
return False
prev = root.val
if root.left:
q.append(root.left)
if root.right:
q.append(root.right)
even ^= 1
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each node is visited exactly once. Space complexity is O(n) due to storing nodes in a queue for BFS traversal at each level. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Check that nodes on the same level follow strict ordering based on level parity.
- question_mark
Ask about handling empty children and single-node levels without skipping checks.
- question_mark
Expect awareness of BFS for layer-by-layer state tracking rather than DFS.
常见陷阱
外企场景- error
Failing to enforce strictly increasing or decreasing order per level.
- error
Misclassifying node parity by level index instead of node values.
- error
Skipping null children and causing incorrect level sequences.
进阶变体
外企场景- arrow_right_alt
Check for Even-Odd properties in an N-ary tree using the same BFS pattern.
- arrow_right_alt
Return the first level that violates Even-Odd rules instead of a boolean.
- arrow_right_alt
Modify the problem to allow non-strict ordering and validate accordingly.