traverse binary tree in zig zag

zig-zag-tree.java

void zigzag(TreeNode curr, ArrayList<LinkedList<Integer>> sol, int level) {
    if(curr == null) return;

    if(sol.size() <= level) {
        sol.add(new LinkedList<>());
    }

    List<Integer> collection  = sol.get(level);
    if(level % 2 == 0) collection.add(curr.val);
    else collection.add(0, curr.val);

    travel(curr.left, sol, level + 1);
    travel(curr.right, sol, level + 1);
}


void zigzag_iter(TreeNode root, ArrayList<LinkedList<Integer>> sol) {
  if (root == null) return;
  
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(root);
  boolean zigzag = false;
  
  while (!queue.isEmpty()) {
    List<Integer> level = new ArrayList<>();
    int cnt = queue.size();
    
    for (int i = 0; i < cnt; i++) {
      TreeNode node = queue.poll();
      if (zigzag) {
            level.add(0, node.val);
      } else {
            level.add(node.val);
      }
      
      if (node.left != null) {
            queue.add(node.left);
      }
      if (node.right != null) {
            queue.add(node.right);
      }
    } // for
    
    res.add(level);
    zigzag = !zigzag;
  } // while
}