(ie. from left to right, then right to left for the next level and alternate between).
[3,9,20,null,null,15,7]
5 / \ 3 20 / \ 7 8 returns zig-zag order [ [3], [20,9], [15,7] ]
The problem can be solved using BFS traversal. Start traversing the tree and move elements in a stack level by level. For each level insert into a list and depending on the level, have a flag to insert from start or end of the list.
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (root == null)
return list;
Queue<TreeNode> stack = new LinkedList();
stack.add(root);
int count = 1;
boolean leftToRight = true;
while (!stack.isEmpty()) {
int futureCount = 0;
LinkedList<Integer> l = new LinkedList<Integer>();
while (count > 0) {
TreeNode t = stack.poll();
if (leftToRight) {
l.add(t.val);
} else {
l.addFirst(t.val);
}
if (t.left != null) {
stack.add(t.left);
futureCount++;
}
if (t.right != null) {
stack.add(t.right);
futureCount++;
}
count--;
}
count = futureCount;
list.add(l);
leftToRight = !leftToRight;
}
return list;
}
static class TreeNode {
TreeNode left;
TreeNode right;
int val;
public TreeNode(int value) {
this.val = value;
}
}}