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;

/**107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]
*/

public class _107 {
	public static class Solution1 {
		public List<List<Integer>> levelOrder(TreeNode root) {
			List<List<Integer>> result = new ArrayList();
			if (root == null) {
				return result;
			}

			Queue<TreeNode> q = new LinkedList();
			q.offer(root);
			while (!q.isEmpty()) {
				List<Integer> thisLevel = new ArrayList<Integer>();
				int qSize = q.size();
				for (int i = 0; i < qSize; i++) {
					TreeNode curr = q.poll();
					thisLevel.add(curr.val);
					if (curr.left != null) {
						q.offer(curr.left);
					}
					if (curr.right != null) {
						q.offer(curr.right);
					}
				}
				result.add(thisLevel);
			}
			Collections.reverse(result);
			return result;
		}
	}
}

@@ -227,403 +227,8 @@
 %0D%0A%0D%0A
-/**107. Binary Tree Level Order Traversal II%0D%0A%0D%0AGiven a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).%0D%0A%0D%0AFor example:%0D%0AGiven binary tree %5B3,9,20,null,null,15,7%5D,%0D%0A%0D%0A    3%0D%0A   / %5C%0D%0A  9  20%0D%0A    /  %5C%0D%0A   15   7%0D%0A%0D%0Areturn its bottom-up level order traversal as:%0D%0A%0D%0A%5B%0D%0A  %5B15,7%5D,%0D%0A  %5B9,20%5D,%0D%0A  %5B3%5D%0D%0A%5D%0D%0A*/%0D%0A%0D%0A
 publ
@@ -244,17 +244,20 @@
 _107 %7B%0D%0A
-%09
+    
 public s
@@ -281,18 +281,24 @@
 ion1 %7B%0D%0A
-%09%09
+        
 public L
@@ -345,19 +345,28 @@
 oot) %7B%0D%0A
-%09%09%09
+            
 List%3CLis
@@ -404,19 +404,28 @@
 ist();%0D%0A
-%09%09%09
+            
 if (root
@@ -441,39 +441,67 @@
  %7B%0D%0A
-%09%09%09%09return result;%0D%0A%09%09%09%7D%0D%0A%0D%0A%09%09%09
+                return result;%0D%0A            %7D%0D%0A            
 Queu
@@ -535,19 +535,28 @@
 ist();%0D%0A
-%09%09%09
+            
 q.offer(
@@ -563,19 +563,28 @@
 root);%0D%0A
-%09%09%09
+            
 while (!
@@ -599,20 +599,32 @@
 y()) %7B%0D%0A
-%09%09%09%09
+                
 List%3CInt
@@ -659,25 +659,30 @@
 ist%3C
-Integer%3E();%0D%0A%09%09%09%09
+%3E();%0D%0A                
 int 
@@ -700,20 +700,32 @@
 ize();%0D%0A
-%09%09%09%09
+                
 for (int
@@ -751,21 +751,36 @@
 i++) %7B%0D%0A
-%09%09%09%09%09
+                    
 TreeNode
@@ -798,21 +798,36 @@
 oll();%0D%0A
-%09%09%09%09%09
+                    
 thisLeve
@@ -844,21 +844,36 @@
 .val);%0D%0A
-%09%09%09%09%09
+                    
 if (curr
@@ -894,155 +894,278 @@
  %7B%0D%0A
-%09%09%09%09%09%09q.offer(curr.left);%0D%0A%09%09%09%09%09%7D%0D%0A%09%09%09%09%09if (curr.right != null) %7B%0D%0A%09%09%09%09%09%09q.offer(curr.right);%0D%0A%09%09%09%09%09%7D%0D%0A%09%09%09%09%7D%0D%0A%09%09%09%09result.add(thisLevel);%0D%0A%09%09%09%7D%0D%0A%09%09%09
+                        q.offer(curr.left);%0D%0A                    %7D%0D%0A                    if (curr.right != null) %7B%0D%0A                        q.offer(curr.right);%0D%0A                    %7D%0D%0A                %7D%0D%0A                result.add(thisLevel);%0D%0A            %7D%0D%0A            
 Coll
@@ -1194,11 +1194,20 @@
 );%0D%0A
-%09%09%09
+            
 retu
@@ -1222,14 +1222,23 @@
 t;%0D%0A
-%09%09%7D%0D%0A%09
+        %7D%0D%0A    
 %7D%0D%0A%7D

refactor 107