Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null)
return ans;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int values = 1;
boolean rightToLeft = false;
while (q.size() != 0) {
ArrayList<Integer> temp = new ArrayList<>();
int tempCounter = values;
values = 0;
while (tempCounter-- > 0) {
TreeNode top = q.poll();
if (rightToLeft)
temp.add(0, top.val);
else
temp.add(top.val);
if (top.left != null) {
q.add(top.left);
values++;
}
if (top.right != null) {
q.add(top.right);
values++;
}
}
ans.add(temp);
rightToLeft = !rightToLeft;
}
return ans;
}
}