题目描述
思路解析动画文字版
记牢这套路: 用 BFS 一层一层取节点, 进每一层先按奇偶下标定好「奇数还是偶数、递增还是递减」两条规则, 再从左到右逐个查。每换一层 prev 都要重置。下面每帧都在套这条规则。
总览 · 一棵树与四层：先看清这棵树。紫色的根是 1, 在第 0 层。它的孩子 10 和 4 在第 1 层; 再往下第 2 层是 3、7、9; 最底下第 3 层是 12、8、6。我们要按层判: 偶数下标的层(0、2)上节点值要是奇数且从左到右严格递增, 奇数下标的层(1、3)上要是偶数且严格递减。先剧透: 这棵树四层全满足, 最后返回 true。
第 0 层 · 偶数层规则：从第 0 层开始, 它是偶数下标的层, 规则是: 节点值要奇数, 而且从左到右严格递增。这层只有根节点一个。递增检查需要一个 prev 记住左边的值, 偶数层把 prev 起步设成 0, 这样第一个节点只要大于 0 就算递增成立。
第 0 层 · 节点 1 查奇偶：查根节点。它的值是 1, 1 是奇数, 符合偶数层要奇数的要求, 奇偶这一关通过。接着查它的单调。
第 0 层 · 节点 1 比大小：查单调。当前 prev 是 0, 节点值是 1, 1 大于 0, 严格递增成立。节点变绿表示这个节点过了。第 0 层只有这一个节点, 整层判过, 把 prev 更新成 1。准备进下一层。
第 1 层 · 奇数层规则：进到第 1 层, 它是奇数下标的层, 规则翻过来: 节点值要偶数, 而且从左到右严格递减。这层有 10 和 4 两个节点。递减检查的 prev 要重置, 这回设成一个比所有值都大的数, 让第一个节点一定小于它。注意层和层之间的值没有大小约束, 所以每换层 prev 必须按新方向重置。
第 1 层 · 节点 10 查奇偶：查这层第一个节点 10。10 是偶数, 符合奇数层要偶数的要求, 奇偶这关过。再查单调。
第 1 层 · 节点 10 比大小：查单调。prev 现在是那个很大的数, 节点值 10 小于它, 严格递减成立。节点 10 过, 把 prev 更新成 10, 接着看右边的 4。
第 1 层 · 节点 4 查奇偶：查这层第二个节点 4。4 是偶数, 符合奇数层要偶数, 奇偶这关过。再看它和左边 10 的大小关系。
第 1 层 · 节点 4 比大小：查单调。prev 是 10, 当前值是 4, 4 小于 10, 严格递减成立。第 1 层两个节点都过, 整层判过。继续往第 2 层走。
第 2 层 · 偶数层规则：到第 2 层, 又是偶数下标的层, 规则切回奇数且严格递增。这层有 3、7、9 三个节点。prev 重新从 0 起步。你看, 上一层还在用递减的大数当 prev, 这一层立刻重置回 0, 这正是「每换层重置 prev」的意义。
第 2 层 · 节点 3 查奇偶：查这层第一个节点 3。3 是奇数, 符合偶数层要奇数, 奇偶这关过。再查单调。
第 2 层 · 节点 3 比大小：查单调。prev 是 0, 节点值 3 大于 0, 严格递增成立。节点 3 过, prev 更新成 3, 看下一个 7。
第 2 层 · 节点 7 查奇偶：查第二个节点 7。7 是奇数, 奇偶这关过。再看它和左边 3 的大小。
第 2 层 · 节点 7 比大小：查单调。prev 是 3, 当前值 7 大于 3, 严格递增成立。节点 7 过, prev 更新成 7, 看最后一个 9。
第 2 层 · 节点 9 查奇偶：查第三个节点 9。9 是奇数, 奇偶这关过。再看它和左边 7 的大小。
第 2 层 · 节点 9 比大小：查单调。prev 是 7, 当前值 9 大于 7, 严格递增成立。第 2 层三个节点全部通过。还剩最后一层第 3 层。
第 3 层 · 奇数层规则：到最后一层第 3 层, 奇数下标, 规则又切回偶数且严格递减。这层有 12、8、6 三个节点。prev 重置成那个很大的数, 让第一个节点一定小于它。
第 3 层 · 节点 12 查奇偶：查这层第一个节点 12。12 是偶数, 符合奇数层要偶数, 奇偶这关过。再查单调。
第 3 层 · 节点 12 比大小：查单调。prev 是那个很大的数, 节点值 12 小于它, 严格递减成立。节点 12 过, prev 更新成 12, 看下一个 8。
第 3 层 · 节点 8 查奇偶：查第二个节点 8。8 是偶数, 奇偶这关过。再看它和左边 12 的大小。
第 3 层 · 节点 8 比大小：查单调。prev 是 12, 当前值 8 小于 12, 严格递减成立。节点 8 过, prev 更新成 8, 看最后一个 6。
第 3 层 · 节点 6 查奇偶：查这层最后一个节点 6。6 是偶数, 奇偶这关过。再看它和左边 8 的大小。
第 3 层 · 节点 6 比大小：查单调。prev 是 8, 当前值 6 小于 8, 严格递减成立。第 3 层三个节点全部通过。所有层都查完了。
收束 · 四层全过, 返回 true：四层从上到下都满足了规则: 偶数层全是奇数且递增, 奇数层全是偶数且递减, 没有一个节点在奇偶或单调上翻车。所以这是一棵奇偶树, 返回 true。回顾整个过程: BFS 一层一层取节点, 进每层先按奇偶下标定规则、重置 prev, 再从左到右逐个查奇偶和单调, 任何一处不满足都会当场返回 false。
边界看三种: 单个奇数根返回 true; 根是偶数直接 false; 偶数层里相邻两个值相等(比如两个 3)因为不满足严格递增也是 false。
面试重点: 按层分组判定用 BFS 最贴合; 用一个布尔 even 翻转代替存层号; 奇数层 prev 要起步成一个很大的数, 才能让第一个节点天然通过递减这关。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# 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 = rightclass 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复杂度
- 时间：O(n)，BFS 把每个节点恰好入队、出队各一次, 每个节点上做的是常数次判断(查奇偶、和 prev 比一次、更新 prev), 所以总时间和节点数成正比, 是 O(n)
- 空间：O(n)，额外空间主要是 BFS 队列。队列里最多同时装着某一层的全部节点, 满二叉树最宽的一层约有 n/2 个节点, 按峰值算就是 O(n); prev 和 even 只是常数个变量
易错点
面试追问把动画讲成自己的话
追问这道题为什么用 BFS 层序遍历, 用 DFS 行不行?
追问怎么知道当前层是偶数下标还是奇数下标, 一定要存层号吗?
追问奇数层的 prev 起步值为什么要设成一个很大的数, 设成 0 行不行?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计最高分的节点数目
LeetCode 2049 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题