class Solution {
  private void traverse(ArrayList<ArrayList<TreeNode>> nodes, int level, TreeNode node) {
    if (node == null) {
      return;
    }

    if (level % 2 == 1) {
      var idx = level >> 1;
      while (nodes.size() <= idx) {
        nodes.addLast(new ArrayList<TreeNode>());
      }

      nodes.get(idx).addLast(node);
    }

    traverse(nodes, level + 1, node.left);
    traverse(nodes, level + 1, node.right);
  }

  private void reverse(ArrayList<TreeNode> level) {
    int i, j;
    for (i = 0, j = level.size() - 1; i < j; ++i, --j) {
      var tmp = level.get(i).val;
      level.get(i).val = level.get(j).val;
      level.get(j).val = tmp;
    }
  }

  public TreeNode reverseOddLevels(TreeNode root) {
    var nodes = new ArrayList<ArrayList<TreeNode>>();
    traverse(nodes, 0, root);

    for (var level : nodes) {
      reverse(level);
    }

    return root;
  }
}