Binary Tree Zigzag Level Order Traversal LeetCode solution in Java

1
/**
2
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
3
 * right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left,
4
 * TreeNode right) { this.val = val; this.left = left; this.right = right; } }
5
 */
6
class Solution {
7
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
8
    Queue<TreeNode> q = new LinkedList<TreeNode>();
9
    List<List<Integer>> res = new ArrayList<>();
10
    if (root == null) {
11
      return res;
12
    }
13
    q.offer(root);
14
    boolean flag = true;
15
    while (!q.isEmpty()) {
16
      int size = q.size();
17
      List<Integer> curr = new ArrayList<>();
18
      for (int i = 0; i < size; i++) {
19
        if (q.peek().left != null) {
20
          q.offer(q.peek().left);
21
        }
22
        if (q.peek().right != null) {
23
          q.offer(q.peek().right);
24
        }
25
        if (flag == true) {
26
          curr.add(q.poll().val);
27
        } else {
28
          curr.add(0, q.poll().val);
29
        }
30
      }
31
      if (flag == true) {
32
        flag = false;
33
      } else {
34
        flag = true;
35
      }
36
      res.add(curr);
37
    }
38
    return res;
39
  }
40
}