/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null)
return new ArrayList();
List<List<Integer>> ans = new ArrayList<>();
Deque<TreeNode>[] stack = new Deque[2];
stack[0] = new LinkedList<>();
stack[1] = new LinkedList<>();
int current = 0;
int next = 1;
stack[current].add(root);
List<Integer> list = new ArrayList<>();
while (!stack[0].isEmpty() || !stack[1].isEmpty()) {
TreeNode node = stack[current].pop();
list.add(node.val);
if (current == 0) {
if (node.left != null) {
stack[next].push(node.left);
}
if (node.right != null) {
stack[next].push(node.right);
}
} else {
if (node.right != null) {
stack[next].push(node.right);
}
if (node.left != null) {
stack[next].push(node.left);
}
}
if (stack[current].isEmpty()) {
ans.add(list);
list = new ArrayList<Integer>();
current = 1 - current;
next = 1 - next;
}
}
return ans;
}
}