class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null)
return res;
Stack<TreeNode> odd = new Stack<TreeNode>();
Stack<TreeNode> even = new Stack<TreeNode>();
odd.push(root);
while(!odd.isEmpty() || !even.isEmpty()){
List<Integer> tem = new ArrayList<Integer>();
while(!odd.isEmpty()){
TreeNode t = odd.pop();
tem.add(t.val);
if(t.left!=null)
even.push(t.left);
if(t.right!=null)
even.push(t.right);
}
res.add(tem);
tem = new ArrayList<Integer>();
while(!even.isEmpty()){
TreeNode t = even.pop();
tem.add(t.val);
if(t.right!=null)
odd.push(t.right);
if(t.left!=null)
odd.push(t.left);
}
if(!tem.isEmpty())
res.add(tem);
}
return res;
}
}