LeetCode 1609中等树 · BST
奇偶树 图解题解
这道题到底在问什么
判定标准只看两件事, 逐层套: 第一, 这一层的值奇偶对不对(偶数层要奇数, 奇数层要偶数); 第二, 这一层从左到右单调对不对(偶数层要严格递增, 奇数层要严格递减)。任何一层、任何一个节点踩中其一就立刻返回 false。本节演示树: 第 0 层是 1, 第 1 层是 10 和 4, 第 2 层是 3、7、9, 第 3 层是 12、8、6。
- 输入
- 第 0 层 [1] (偶数层)
- 输出
- 1 是奇数, 单个节点天然递增, 过
- 输入
- 第 1 层 [10, 4] (奇数层)
- 输出
- 都是偶数, 10 到 4 严格递减, 过
- 输入
- 第 2 层 [3, 7, 9] (偶数层)
- 输出
- 都是奇数, 3 到 7 到 9 严格递增, 过
最优解：一步一步想明白
- 3记牢这套路: 用 BFS 一层一层取节点, 进每一层先按奇偶下标定好「奇数还是偶数、递增还是递减」两条规则, 再从左到右逐个查。每换一层 prev 都要重置。下面每帧都在套这条规则。
- 4按层判: 偶数层奇增, 奇数层偶减先看清这棵树。紫色的根是 1, 在第 0 层。它的孩子 10 和 4 在第 1 层; 再往下第 2 层是 3、7、9; 最底下第 3 层是 12、8、6。我们要按层判: 偶数下标的层(0、2)上节点值要是奇数且从左到右严格递增, 奇数下标的层(1、3)上要是偶数且严格递减。先剧透: 这棵树四层全满足, 最后返回 true。
- 5偶数层: 要奇数, 要严格递增, prev 起步 0从第 0 层开始, 它是偶数下标的层, 规则是: 节点值要奇数, 而且从左到右严格递增。这层只有根节点一个。递增检查需要一个 prev 记住左边的值, 偶数层把 prev 起步设成 0, 这样第一个节点只要大于 0 就算递增成立。
- 6节点值 1 是奇数, 奇偶这关过查根节点。它的值是 1, 1 是奇数, 符合偶数层要奇数的要求, 奇偶这一关通过。接着查它的单调。
- 71 大于 prev 0, 第 0 层整层过查单调。当前 prev 是 0, 节点值是 1, 1 大于 0, 严格递增成立。节点变绿表示这个节点过了。第 0 层只有这一个节点, 整层判过, 把 prev 更新成 1。准备进下一层。
- 8奇数层: 要偶数, 要严格递减, prev 起步 大数进到第 1 层, 它是奇数下标的层, 规则翻过来: 节点值要偶数, 而且从左到右严格递减。这层有 10 和 4 两个节点。递减检查的 prev 要重置, 这回设成一个比所有值都大的数, 让第一个节点一定小于它。注意层和层之间的值没有大小约束, 所以每换层 prev 必须按新方向重置。
- 9节点值 10 是偶数, 奇偶这关过查这层第一个节点 10。10 是偶数, 符合奇数层要偶数的要求, 奇偶这关过。再查单调。
- 1010 小于 prev 大数, 单调过查单调。prev 现在是那个很大的数, 节点值 10 小于它, 严格递减成立。节点 10 过, 把 prev 更新成 10, 接着看右边的 4。
- 11节点值 4 是偶数, 奇偶这关过查这层第二个节点 4。4 是偶数, 符合奇数层要偶数, 奇偶这关过。再看它和左边 10 的大小关系。
- 124 小于 prev 10, 第 1 层整层过查单调。prev 是 10, 当前值是 4, 4 小于 10, 严格递减成立。第 1 层两个节点都过, 整层判过。继续往第 2 层走。
- 13偶数层: 回到奇数 + 递增, prev 重置 0到第 2 层, 又是偶数下标的层, 规则切回奇数且严格递增。这层有 3、7、9 三个节点。prev 重新从 0 起步。你看, 上一层还在用递减的大数当 prev, 这一层立刻重置回 0, 这正是「每换层重置 prev」的意义。
- 14节点值 3 是奇数, 奇偶这关过查这层第一个节点 3。3 是奇数, 符合偶数层要奇数, 奇偶这关过。再查单调。
- 153 大于 prev 0, 单调过查单调。prev 是 0, 节点值 3 大于 0, 严格递增成立。节点 3 过, prev 更新成 3, 看下一个 7。
- 16节点值 7 是奇数, 奇偶这关过查第二个节点 7。7 是奇数, 奇偶这关过。再看它和左边 3 的大小。
- 177 大于 prev 3, 单调过查单调。prev 是 3, 当前值 7 大于 3, 严格递增成立。节点 7 过, prev 更新成 7, 看最后一个 9。
- 18节点值 9 是奇数, 奇偶这关过查第三个节点 9。9 是奇数, 奇偶这关过。再看它和左边 7 的大小。
- 199 大于 prev 7, 第 2 层整层过查单调。prev 是 7, 当前值 9 大于 7, 严格递增成立。第 2 层三个节点全部通过。还剩最后一层第 3 层。
- 20奇数层: 偶数 + 递减, prev 重置 大数到最后一层第 3 层, 奇数下标, 规则又切回偶数且严格递减。这层有 12、8、6 三个节点。prev 重置成那个很大的数, 让第一个节点一定小于它。
- 21节点值 12 是偶数, 奇偶这关过查这层第一个节点 12。12 是偶数, 符合奇数层要偶数, 奇偶这关过。再查单调。
- 2212 小于 prev 大数, 单调过查单调。prev 是那个很大的数, 节点值 12 小于它, 严格递减成立。节点 12 过, prev 更新成 12, 看下一个 8。
- 23节点值 8 是偶数, 奇偶这关过查第二个节点 8。8 是偶数, 奇偶这关过。再看它和左边 12 的大小。
- 248 小于 prev 12, 单调过查单调。prev 是 12, 当前值 8 小于 12, 严格递减成立。节点 8 过, prev 更新成 8, 看最后一个 6。
- 25节点值 6 是偶数, 奇偶这关过查这层最后一个节点 6。6 是偶数, 奇偶这关过。再看它和左边 8 的大小。
- 266 小于 prev 8, 第 3 层整层过查单调。prev 是 8, 当前值 6 小于 8, 严格递减成立。第 3 层三个节点全部通过。所有层都查完了。
- 27没有一层违规, 整棵树是奇偶树四层从上到下都满足了规则: 偶数层全是奇数且递增, 奇数层全是偶数且递减, 没有一个节点在奇偶或单调上翻车。所以这是一棵奇偶树, 返回 true。回顾整个过程: BFS 一层一层取节点, 进每层先按奇偶下标定规则、重置 prev, 再从左到右逐个查奇偶和单调, 任何一处不满足都会当场返回 false。
⚠️ 容易写错的地方
✗ 错：换层后还沿用上一层的 prev 去比大小
✓ 对：每进入新的一层都重置 prev: 偶数层重置成 0, 奇数层重置成一个很大的数
层与层之间的值没有大小约束, 不重置会拿上层的值误判本层第一个节点, 而且递增递减方向每层还相反
✗ 错：把「严格递增/递减」写成了允许相等
✓ 对：偶数层必须当前严格大于 prev, 奇数层必须当前严格小于 prev, 相等就判 false
题目要求严格单调, 相邻两个值相等(比如一层里出现两个 3)是不允许的, 用大于等于或小于等于会漏判
✗ 错：只查了单调, 忘了先查奇偶; 或只查奇偶忘了单调
✓ 对：每个节点两关都要查: 偶数层既要奇数又要递增, 奇数层既要偶数又要递减
两个条件缺一不可。比如值递增没问题但出现了偶数在偶数层, 一样要返回 false
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class 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 = 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 TrueC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isEvenOddTree(TreeNode* root) {
int even = 1;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
int prev = even ? 0 : 1e7;
for (int n = q.size(); n; --n) {
root = q.front();
q.pop();
if (even && (root->val % 2 == 0 || prev >= root->val)) {
return false;
}
if (!even && (root->val % 2 == 1 || prev <= root->val)) {
return false;
}
prev = root->val;
if (root->left) {
q.push(root->left);
}
if (root->right) {
q.push(root->right);
}
}
even ^= 1;
}
return true;
}
};Java
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public boolean isEvenOddTree(TreeNode root) {
boolean even = true;
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int prev = even ? 0 : 1000001;
for (int n = q.size(); n > 0; --n) {
root = q.pollFirst();
if (even && (root.val % 2 == 0 || prev >= root.val)) {
return false;
}
if (!even && (root.val % 2 == 1 || prev <= root.val)) {
return false;
}
prev = root.val;
if (root.left != null) {
q.offer(root.left);
}
if (root.right != null) {
q.offer(root.right);
}
}
even = !even;
}
return true;
}
}复杂度
时间
O(n)
BFS 把每个节点恰好入队、出队各一次, 每个节点上做的是常数次判断(查奇偶、和 prev 比一次、更新 prev), 所以总时间和节点数成正比, 是 O(n)
空间
O(n)
额外空间主要是 BFS 队列。队列里最多同时装着某一层的全部节点, 满二叉树最宽的一层约有 n/2 个节点, 按峰值算就是 O(n); prev 和 even 只是常数个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 奇偶树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用 BFS 层序遍历, 用 DFS 行不行?+
判定是按层分组的: 不同层规则不同(偶数层奇增、奇数层偶减), 而且同一层要从左到右依次比较相邻值。BFS 用队列天然一层一层、从左到右把节点取出来, 和判定方式完全贴合, 写起来最顺。DFS 也能做, 但要给每个节点带上它的层号, 还要为每一层单独维护「这一层上一个值」, 实现更绕, 没有 BFS 直观。
怎么知道当前层是偶数下标还是奇数下标, 一定要存层号吗?+
不用单独存层号。用一个布尔变量 even 表示当前层是不是偶数下标层, 根那层把它设成真; 每处理完一整层就把它翻转一次, 真变假、假变真。这样始终知道当前层的奇偶性, 比给每个节点存一个层号更省事。
奇数层的 prev 起步值为什么要设成一个很大的数, 设成 0 行不行?+
不行。奇数层要严格递减, 判定是「当前值要小于 prev」。如果 prev 起步是 0, 第一个节点的值(至少是 1)不可能小于 0, 第一个节点就被误判失败了。所以要把起步设成比所有可能的值都大的数, 题面值不超过一百万, 用一百万零一或者直接用语言里的无穷大都行, 这样第一个节点一定小于它、天然通过, 真正的递减比较从第二个节点才开始。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 奇偶树 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。