⚡Flashcard Drill➔
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

  1. At an odd level, the left-to-right order of the nodes must be reversed, which pairs node i with node n-1-i.
  2. 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).
  3. The level parity determines whether a swap happens.
  4. 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 is left.left with right.right and left.right with right.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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems