How can I reverse the values at odd levels of a binary tree?

You can reverse the values by performing a level-order traversal, identifying odd levels, and reversing the values of nodes at those levels.

What is a perfect binary tree?

A perfect binary tree is a binary tree where each non-leaf node has exactly two children, and all leaves are at the same level.

What traversal method is best for this problem?

Both Depth-First Search (DFS) and Breadth-First Search (BFS) can be used effectively. BFS is particularly useful for level-order traversal.

How do I handle edge cases like a single-node tree?

For a single-node tree, there are no odd levels to reverse, so the tree remains unchanged.

Can I optimize space usage for this problem?

Yes, you can minimize space usage by reversing the nodes in-place or using a two-pointer technique instead of storing all values at odd levels.

#2415

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

反转二叉树的奇数层

给你一棵完美二叉树的根节点 root ，请你反转这棵树中每个奇数层的节点值。例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。反转后，返回树的根节点。完美二叉树需满足：二叉树的所有父节点都有两…

树深度优先搜索广度优先搜索二叉树

题目描述

给你一棵完美二叉树的根节点 root ，请你反转这棵树中每个奇数层的节点值。

例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。

反转后，返回树的根节点。

完美二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。

节点的层数等于该节点到根节点之间的边数。

示例 1：

输入：root = [2,3,5,8,13,21,34]
输出：[2,5,3,8,13,21,34]
解释：
这棵树只有一个奇数层。
在第 1 层的节点分别是 3、5 ，反转后为 5、3 。

示例 2：

输入：root = [7,13,11]
输出：[7,11,13]
解释： 
在第 1 层的节点分别是 13、11 ，反转后为 11、13 。

示例 3：

输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
输出：[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
解释：奇数层由非零值组成。
在第 1 层的节点分别是 1、2 ，反转后为 2、1 。
在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。

提示：

树中的节点数目在范围 [1, 2¹⁴] 内
0 <= Node.val <= 10⁵
root 是一棵完美二叉树

lightbulb

解题思路

方法一：BFS

我们可以使用广度优先搜索的方法，用一个队列 $q$ 来存储每一层的节点，用一个变量 $i$ 记录当前层数。若 $i$ 为奇数，则将当前层的节点值反转。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是二叉树的节点数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

# 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 reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        q = deque([root])
        i = 0
        while q:
            if i & 1:
                l, r = 0, len(q) - 1
                while l < r:
                    q[l].val, q[r].val = q[r].val, q[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

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidates should be able to implement binary tree traversal techniques efficiently.
question_mark
Look for the candidate's ability to identify and reverse values at odd levels correctly.
question_mark
Assess if the candidate can optimize space complexity while ensuring the problem's constraints are met.

warning

常见陷阱

外企场景

error
Incorrectly reversing nodes at even levels instead of odd levels.
error
Failing to maintain the tree structure during reversal, causing the tree to become unbalanced.
error
Not handling edge cases where the tree has very few nodes, such as a single-node tree or a tree with only two levels.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider implementing the solution iteratively rather than recursively.
arrow_right_alt
Challenge the candidate to optimize for space by modifying the tree in-place.
arrow_right_alt
Extend the problem to reverse values on both odd and even levels or implement other forms of level-wise node manipulation.

help

常见问题

外企场景

继续练习

#2385 感染二叉树需要的总时间 #2458 移除子树后的二叉树高度 #2641 二叉树的堂兄弟节点 II