/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
LinkedList<TreeNode> list = new LinkedList<>();
//show value should be added from which direction
boolean leftToRight = true;
list.add(root);
while(!list.isEmpty()){
//how many value should be added into res in this level
int size = list.size();
LinkedList<Integer> clist = new LinkedList<>();
if(leftToRight){
for(int i = 0; i < size; i++){
TreeNode curr = list.remove(0);
clist.add(curr.val);
//add val to list from left to right
if(curr.left != null) list.add(curr.left);
if(curr.right != null) list.add(curr.right);
}
}else{
for(int i = 0; i < size; i++){
TreeNode curr = list.remove(list.size() - 1);
clist.add(curr.val);
//add val to list from right to left
if(curr.right != null) list.add(0, curr.right);
if(curr.left != null) list.add(0, curr.left);
}
}
res.add(clist);
//change the direction
leftToRight = !leftToRight;
}
return res;
}
}
