LeetCode Solutions Blog

Reverse Odd Levels of Binary Tree

Difficulty: Medium

Problem Description

Given the root of a perfect binary tree, reverse the node values at each odd level of the tree. Return the root of the reversed tree.

Key Insights

The binary tree is perfect, meaning all levels are fully filled, and all leaves are at the same depth.
Nodes at even levels remain unchanged, while nodes at odd levels need to be reversed.
A breadth-first traversal can help us easily access nodes level by level.
We can store nodes at odd levels in a list and reverse that list to update the tree.

Space and Time Complexity

Time Complexity: O(n) - We visit every node in the tree once. Space Complexity: O(n) - We may need to store nodes at a level in a list.

Solution

The solution involves using a breadth-first search (BFS) approach to traverse the binary tree level by level. We will use a queue to facilitate the BFS. For each level, we will check if it is an odd level; if it is, we will collect the node values in a list, reverse that list, and then reassign the values back to the nodes in the tree.

Code Solutions

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def reverseOddLevels(root: TreeNode) -> TreeNode:
    if not root:
        return None

    queue = deque([root])
    level = 0

    while queue:
        level_size = len(queue)
        current_level_values = []

        # Collect node values at the current level
        for _ in range(level_size):
            node = queue.popleft()
            current_level_values.append(node)

            if node.left:  # Enqueue left child
                queue.append(node.left)
            if node.right:  # Enqueue right child
                queue.append(node.right)

        # Reverse values at odd levels
        if level % 2 == 1:
            for i in range(level_size):
                current_level_values[i].val = current_level_values[level_size - 1 - i].val

        level += 1

    return root