package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


/**
 * 103. Binary Tree Zigzag Level Order Traversal  
 * 
Given a binary tree, return the zigzag level order traversal of its nodes' values.
 (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]
*/
public class _103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList();
        List<List<Integer>> levels = new ArrayList();
        if (root == null) {
            return levels;
        }
        q.offer(root);
        boolean forward = true;
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> level = new ArrayList();
            for (int i = 0; i < size; i++) {
                TreeNode curr = q.poll();
                level.add(curr.val);
                if (curr.left != null) {
                    q.offer(curr.left);
                }
                if (curr.right != null) {
                    q.offer(curr.right);
                }
            }
            if (forward) {
                forward = false;
                levels.add(level);
            } else {
                Collections.reverse(level);
                levels.add(level);
                forward = true;
            }
        }
        return levels;
    }
}

@@ -213,17 +213,16 @@
 Queue;%0A%0A
-%0A
 /**%0A * 1
@@ -269,14 +269,11 @@
 rsal
-  
 %0A *
- 
 %0AGiv
@@ -634,16 +634,56 @@
  _103 %7B%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -747,16 +747,20 @@
         
+   
+ 
 Queue%3CTr
@@ -781,32 +781,36 @@
 w LinkedList();%0A
+    
         List%3CLis
@@ -851,24 +851,28 @@
 ();%0A        
+ 
+   
 if (root == 
@@ -883,32 +883,36 @@
 ) %7B%0A            
+  
+  
 return levels;%0A 
@@ -910,34 +910,42 @@
 levels;%0A        
-%7D%0A
+    %7D%0A    
         q.offer(
@@ -959,16 +959,20 @@
         
+    
 boolean 
@@ -995,16 +995,20 @@
         
+  
+  
 while (!
@@ -1034,16 +1034,20 @@
         
+   
+ 
 int size
@@ -1055,24 +1055,28 @@
 = q.size();%0A
+    
             
@@ -1126,16 +1126,20 @@
         
+    
 for (int
@@ -1179,16 +1179,20 @@
         
+ 
+   
 TreeNode
@@ -1221,24 +1221,28 @@
             
+    
 level.add(cu
@@ -1246,24 +1246,28 @@
 (curr.val);%0A
+    
             
@@ -1307,32 +1307,36 @@
                 
+    
 q.offer(curr.lef
@@ -1347,34 +1347,41 @@
                 
-%7D%0A
+    %7D%0A   
                 
@@ -1372,32 +1372,33 @@
                 
+ 
 if (curr.right !
@@ -1399,32 +1399,36 @@
 ight != null) %7B%0A
+    
                 
@@ -1460,34 +1460,40 @@
                 
-%7D%0A
+    %7D%0A  
             %7D%0A  
@@ -1480,34 +1480,40 @@
 %7D%0A              
-%7D%0A
+  %7D%0A    
             if (
@@ -1519,24 +1519,28 @@
 (forward) %7B%0A
+    
             
@@ -1568,32 +1568,36 @@
                 
+    
 levels.add(level
@@ -1611,16 +1611,20 @@
         
+    
 %7D else %7B
@@ -1640,16 +1640,20 @@
         
+   
+ 
 Collecti
@@ -1664,32 +1664,36 @@
 reverse(level);%0A
+    
                 
@@ -1719,32 +1719,36 @@
                 
+    
 forward = true;%0A
@@ -1759,26 +1759,33 @@
         
+ 
-%7D%0A
+   %7D%0A   
         
 %7D%0A      
@@ -1768,34 +1768,39 @@
    %7D%0A           
+ 
 %7D%0A
+    
         return l
@@ -1802,20 +1802,30 @@
 urn levels;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 103