Untitled

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class ReverseOddLevelsDFS {
    public TreeNode reverseOddLevels(TreeNode root) {
        if (root == null) return null;

        // Reverse odd levels of the tree
        reverseOddLevelsHelper(root.left, root.right, 1); // Start at level 1
        return root;
    }

    private void reverseOddLevelsHelper(TreeNode left, TreeNode right, int level) {
        // Base case: If either node is null, return
        if (left == null || right == null) return;

        // Reverse values at odd levels
        if (level % 2 == 1) {
            int temp = left.val;
            left.val = right.val;
            right.val = temp;
        }

        // Recur for the next level (both children)
        reverseOddLevelsHelper(left.left, right.right, level + 1);
        reverseOddLevelsHelper(left.right, right.left, level + 1);
    }

    public static void main(String[] args) {
        ReverseOddLevelsDFS solution = new ReverseOddLevelsDFS();

        // Example 1
        TreeNode root1 = new TreeNode(2);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(5);
        root1.left.left = new TreeNode(8);
        root1.left.right = new TreeNode(13);
        root1.right.left = new TreeNode(21);
        root1.right.right = new TreeNode(34);

        TreeNode result1 = solution.reverseOddLevels(root1);
        printTree(result1); // Expected Output: [2,5,3,8,13,21,34]
    }

    private static void printTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        System.out.println();
    }
}