# Java iterative and recursive solutions.

• ``````// bfs
public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
int l = 0;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node != null) {
}
}
if (!level.isEmpty()) {
if (l % 2 == 1) {
Collections.reverse(level);
}
}
l++;
}
return ret;
}

// dfs recursively
public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
dfs(root, 0, ret);
return ret;
}

private void dfs(TreeNode node, int l, List<List<Integer>> ret) {
if (node != null) {
if (l == ret.size()) {
List<Integer> level = new ArrayList<>();
}
if (l % 2 == 1) {
ret.get(l).add(0, node.val);  // insert at the beginning
} else {
}
dfs(node.left, l+1, ret);
dfs(node.right, l+1, ret);
}
}

// dfs iteratively
// import javafx.util.Pair;
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
Deque<Pair<TreeNode, Integer>> stack = new LinkedList<>();
stack.push(new Pair(root, 0));
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> p = stack.pop();
TreeNode node = p.getKey();
int l = p.getValue();
if (node != null) {
if (l == ret.size()) {
}
if (l % 2 == 1) {