题目描述
思路解析
一句话答案：LeetCode 1609 奇偶树：判断二叉树是否逐层达标——偶数层的值全为奇数且严格递增，奇数层全为偶数且严格递减。用 BFS 一层层取节点、拿 prev 现场比大小，时间 O(n)。
什么样的二叉树才算奇偶树
给一棵二叉树，判断它是不是奇偶树，规则只两条、逐层套用。根这层记作第 0 层，往下依次编号。偶数编号的层，节点值要全是奇数、且从左到右严格递增；奇数编号的层，要全是偶数、且严格递减。一层里有一个节点奇偶或单调不达标，整棵树立刻判 false。题面示范树第 0 层 1，第 1 层 10 和 4，第 2 层 3、7、9，第 3 层 12、8、6，四层合规，返回 true。
为什么判定得按层来，单看一个节点不够
难在这些规则没一条只盯单个节点就能拍板。判奇偶简单，可「严格递增」「严格递减」比的是它和同层左邻的大小——得先知道它在第几层、该增该减、左邻是多少，顺一条路往下深走时这些都不知道。所以自然的走法就是同层凑齐、横着过，从左到右一个个取，一层扫完再落到下一层。
层序取节点，每层先把两条规则定死
用队列做层序遍历，外层循环每圈处理一整层。进层前先按这层的编号奇偶定规则：偶数层要奇数且递增，奇数层要偶数且递减。不必给节点存层号，用布尔标记 even 记住当前层是不是偶数层，根那层设真，每处理完一层翻转一次，层的奇偶就一直对。
递增递减靠一个 prev 变量盯着左边刚过的值。进偶数层前把 prev 设成 0，第一个节点大于 0 就先站得住；进奇数层前设成一个比所有节点值都大的数，第一个节点一定小于它、天然放行。每个节点过两关：先看奇偶，再和 prev 比一次，偶数层要当前值＞prev，奇数层要＜prev；两关全过才更新 prev、看右边。
拿这棵四层的树逐层验过去
从第 0 层开始，偶数层，prev 起步 0。根是 1，奇数，过奇偶；1＞0，递增成立，prev 变 1。这层就一个节点，翻到奇数层。第 1 层 prev 重置成很大的数：10 偶数，10＜很大的数，prev 变 10；4 偶数，4＜10，prev 变 4。整层过，翻回偶数层。
第 2 层 prev 从 0 起步。3 奇数，3＞0，prev 变 3；7 奇数，7＞3，prev 变 7；9 奇数，9＞7，都过。翻到奇数层，第 3 层 prev 又重置成很大的数。12 偶数，12＜很大的数，prev 变 12；8＜12，prev 变 8；6＜8。四层没有节点掉链子，判定为 true。
换层忘了重置 prev、或把严格写松，会漏判什么
常被栽的一步是换层不重置 prev。层间的值本没有大小约束，上层递减留的小值被下层递增拿来比，第一个节点几乎必然误判；何况方向每层相反，不重置连方向都错。另一个坑是把严格写成允许相等：一层里相邻两个 3 就不满足，＞=或＜=会放它过去。还有人只查单调忘了奇偶——偶数混进偶数层，哪怕值在递增也返回 false。
复杂度上，BFS 让每个节点入队、出队各一次，每个节点只做奇偶判断、和 prev 比一次、更新 prev 几步常数，时间 O(n)；额外空间是队列，峰值约最宽一层的 n/2 个节点，空间 O(n)。边界先想清：一个奇数根返回 true；根是偶数第一关就挂，返回 false；偶数层相邻两值相等、单调卡死，同样 false。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套路: 用 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题