2415. Reverse Odd Levels of Binary Tree

MediumView on LeetCode

Tree Depth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

Reverse odd levels of binary tree. BFS level-order traversal, collect nodes at odd levels, swap their values.

Algorithm

1BFS. Track level. At odd levels: collect all node values, reverse them in-place.

Common Pitfalls

•Perfect binary tree. Only values need to be swapped, not nodes. Collect level values, reverse array.

2415.cs


// Approach: BFS level order; collect odd-level nodes and swap their values symmetrically.
// Time: O(n) Space: O(n)

//Definition for a binary tree node.
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public TreeNode ReverseOddLevels(TreeNode root)
    {
        Dfs(root.left, root.right, true);
        return root;
    }

    private void Dfs(TreeNode left, TreeNode right, bool isOddLevel)
    {
        if (left == null)
            return;
        if (isOddLevel)
        {
            int val = left.val;
            left.val = right.val;
            right.val = val;
        }
        Dfs(left.left, right.right, !isOddLevel);
        Dfs(left.right, right.left, !isOddLevel);
    }
}

Was this solution helpful?