题目描述
思路解析动画文字版
记牢这一句:偶数层不碰,奇数层用左右指针成对换值。下面从第 0 层开始,一层一层往下走。
先看全树 · 三层结构：先把这棵树看清楚。它一共三层:最上面第 0 层是根 2;第 1 层是它的两个孩子 3 和 5;最下面第 2 层是四个叶子 8、13、21、34。层号从根算起是 0,往下依次加一。我们要动的只有奇数层,这棵树里就是第 1 层。
层序遍历开始 · 第 0 层：层序遍历从根开始。把根 2 放进队列,现在处理第 0 层,这一层只有它一个节点。先看层号,i 等于 0。判断奇偶:0 是偶数,所以这一层不需要反转。
第 0 层是偶数层 · 不反转,孩子入队：第 0 层是偶数层,直接跳过反转,值一个都不动。接着把根 2 的两个孩子按从左到右的顺序入队:先 3 后 5。它们组成下一层,也就是第 1 层的待处理队列。第 0 层就算处理完了。
进入第 1 层 · 收集本层节点：轮到第 1 层。这一层从左到右是两个节点 3 和 5,已经在队列里排好。处理任何一层的第一步,都是先问一句:这一层的层号是奇数还是偶数。这里 i 等于 1。
判断层号奇偶 · 1 是奇数：算一下,1 除以 2 余 1,所以 1 是奇数,这是一个奇数层。奇数层就要做反转。反转的目标很明确:把这一排节点的值,从 3、5 变成 5、3,让整层顺序颠倒过来。
奇数层反转 · 摆好左右指针：反转用一对指针来做。左指针 l 站在这一层最左边,指着 3;右指针 r 站在最右边,指着 5。它们会从两头往中间走,一路把对称位置上的两个值成对交换。这一层只有两个节点,所以走一次就够了。
读取两端的值 · 准备交换：交换前先把两端的值拿到手:左指针那里是 3,右指针那里是 5。注意我们只交换这两个节点里存的数字,节点本身和它连着的子树不动。对完美二叉树来说,只换值就等于把这一层的顺序翻过来。
交换完成 · 第 1 层变为 5, 3：一交换,左边的节点里现在是 5,右边的节点里现在是 3。你看树上第 1 层,已经从 3、5 变成了 5、3。这一步只改了两个节点存的数字,连线和它们各自的孩子都还在原地。
指针交叉 · 本层反转结束：交换后左指针往右挪一步、右指针往左挪一步,l 从 0 走到 1、r 从 1 走到 0,两个指针交叉了。指针交叉或相遇就代表这一层从两头到中间都换过了,反转到此结束。现在第 1 层稳稳是 5、3。
确认第 1 层 · 5 在左,3 在右：再确认一眼:第 0 层的根还是 2 没动,第 1 层已经反转成 5 在左、3 在右。奇数层的活儿干完了,接下来要为下一层做准备,把第 1 层这两个节点的孩子入队。
入队 · 左节点的两个孩子 8, 13：先看第 1 层左边这个节点,它现在存着 5。孩子按位置算是它下面挂的 8 和 13,注意交换的只是值,孩子还挂在原来的节点上。把 8、13 按从左到右的顺序放进队列。
入队 · 右节点的两个孩子 21, 34：再看第 1 层右边这个节点,它现在存着 3,下面挂的孩子是 21 和 34,继续入队。现在下一层的队列凑齐了,从左到右是 8、13、21、34,正好是第 2 层的四个节点。
进入第 2 层 · 收集本层节点：来到第 2 层,这一层从左到右是四个叶子 8、13、21、34。老规矩,先问层号奇偶。i 等于 2。
第 2 层是偶数层 · 跳过反转：2 除以 2 余 0,是偶数,所以第 2 层跳过反转,四个值原封不动。接下来只需把这一层的节点一个个出队即可,因为它们都是叶子,底下没有孩子要入队了。
出队 · 8(叶子)：把第 2 层第一个节点 8 出队。它是叶子,底下没有孩子,所以什么都不用入队,处理它就是走个过场。
出队 · 13(叶子)：再出队 13,同样是叶子。队列里的节点一个个被取走,底下没有新节点补进来,队列只会越来越短。
出队 · 21(叶子)：出队 21,还是叶子。队列里现在只剩最后一个 34 了。
出队 · 34(叶子)：出队最后一个 34,叶子,没有孩子。队列被取空了,再也没有下一层要处理。
队列为空 · 层序遍历结束：队列空了,层序遍历结束。回头看这一趟:第 0 层偶数不动,第 1 层奇数已经反转成 5、3,第 2 层偶数不动。整棵树该翻的都翻了。
最终结果 · 奇数层已反转：最终这棵树,层序读出来就是 2、5、3、8、13、21、34。跟一开始预告的答案完全对上。全程唯一被改动的,就是第 1 层这个奇数层,3 和 5 交换成了 5 和 3。
回放 · 只有奇数层顺序颠倒：把整件事收成一句:偶数层第 0 层和第 2 层原样不动,只有奇数层第 1 层被颠倒了顺序,从 3、5 变成 5、3。反转靠的是左右指针成对交换节点里的值,树的结构和连线自始至终没变。
边界想清:单节点只有偶数第 0 层原样不动;三节点树反转第 1 层;七节点树只翻第 1 层、第 2 层保持原序。
面试重点:完美树对称所以只换值即可、可用镜像双指针递归、时间 O(n) 空间 O(n)。
参考代码
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 reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]: q = deque([root]) i = 0 while q: if i & 1: level = list(q) l, r = 0, len(level) - 1 while l < r: level[l].val, level[r].val = level[r].val, level[l].val l, r = l + 1, r - 1 for _ in range(len(q)): node = q.popleft() if node.left: q.append(node.left) q.append(node.right) i += 1 return root复杂度
- 时间：O(n)，n 是节点总数。层序遍历里每个节点恰好入队、出队各一次,是常数操作;奇数层的成对交换,所有层加起来交换的次数不超过节点总数的一半。合起来随节点数线性增长
- 空间：O(n)，按峰值算。额外开销主要是那个队列,它最多同时装下最宽的一层。完美二叉树最底层约占一半节点,所以队列峰值是 O(n) 量级,不额外开与节点数无关的大表
易错点
面试追问把动画讲成自己的话
追问为什么只交换值就能反转整层,不用真的调整节点位置?
追问除了层序遍历,还有别的写法吗?
追问时间和空间复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
树上最大得分和路径
LeetCode 2467 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题