NeetCode #426LC-2415MediumTrees
← Back to All Problems#426 · #2415 · Reverse Odd Levels of Binary Tree(反转二叉树的奇数层)
📌 Problem Statement & Constraints
Given the root of a perfect binary tree, reverse the node values at each odd level (the root is level 0). Return the root. Constraints: the number of nodes is in
[1, 2^14 - 1], 1 <= Node.val <= 10^5.💡 Core Algorithmic Approaches
- At an odd level, the left-to-right order of the nodes must be reversed, which pairs node
iwith noden-1-i. - A simultaneous DFS from the leftmost and rightmost nodes of a level achieves this: swap their values, then recurse into
(left.left, right.right)and(left.right, right.left). - The level parity determines whether a swap happens.
- Because the tree is perfect, the two pointers stay aligned on the same level.
💻 Benchmark Python3 Implementation
class Solution:
def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(left: Optional[TreeNode], right: Optional[TreeNode], level: int) -> None:
if not left or not right:
return
if level % 2 == 1:
left.val, right.val = right.val, left.val # swap mirrored nodes
# mirrored recursion keeps the pairs aligned on the same level
dfs(left.left, right.right, level + 1)
dfs(left.right, right.left, level + 1)
if root:
dfs(root.left, root.right, 1) # level 1 is the first odd level
return root⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node participates in one swap or none.
💾 Space Complexity
O(log n) for the recursion stack (the tree is perfect).
⚠️ Interview Pitfalls & Follow-ups
- Starting the level at 0: the children are at level 1, which is the first odd level.
- Recursing into
(left.left, right.left): the mirrored pairing isleft.leftwithright.rightandleft.rightwithright.left. - Reversing the node pointers instead of the values: the problem asks to reverse the values.
- Using a level-order traversal and reversing the list: it works but allocates O(w) per level, where w is the width.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.