Binary Tree Zigzag Level Order Traversal

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
12         List<List<Integer>> result = new ArrayList<>();
13         if (root == null) {
14             return result;
15         }
16         Queue<TreeNode> queue = new LinkedList<TreeNode>();
17         Stack<TreeNode> stack = new Stack<>();
18         queue.offer(root);
19         boolean flag = true;
20         while (!queue.isEmpty()) {
21             List<Integer> list = new ArrayList<>();
22             int size = queue.size();
23             for (int i = 0; i < size; i++) {
24                 TreeNode node = queue.poll();
25                 list.add(node.val);
26                 if (flag == false) {
27                     if (node.right != null) {
28                         stack.push(node.right);
29                     }
30                     if (node.left != null) {
31                         stack.push(node.left);
32                     }
33                 } else {
34                     stack.push(node);
35                 }
36             }
37             result.add(list);
38             while (!stack.empty()) {
39                 if (flag == false) {
40                     queue.offer(stack.pop());
41                 } else {
42                     TreeNode temp = stack.pop();
43                     if (temp.right != null) {
44                         queue.offer(temp.right);
45                     }
46                     if (temp.left != null) {
47                         queue.offer(temp.left);
48                     }
49                 }
50             }
51             flag = !flag;
52         }
53         return result;
54     }
55 }