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 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);//this is the only line that gets added/changed to the previous solution.
		return result;
	}
}

@@ -223,18 +223,16 @@
 eue;%0D%0A%0D%0A
-%0D%0A
 /**107. 
@@ -639,16 +639,51 @@
 _107 %7B%0D%0A
+%09public static class Solution1 %7B%0D%0A%09
 %09public 
@@ -733,16 +733,17 @@
 t) %7B%0D%0A%09%09
+%09
 List%3CLis
@@ -781,16 +781,17 @@
 ist();%0D%0A
+%09
 %09%09if (ro
@@ -808,16 +808,17 @@
 ) %7B%0D%0A%09%09%09
+%09
 return r
@@ -825,16 +825,17 @@
 esult;%0D%0A
+%09
 %09%09%7D%0D%0A%0D%0A%09
@@ -835,16 +835,17 @@
 %09%7D%0D%0A%0D%0A%09%09
+%09
 Queue%3CTr
@@ -875,16 +875,17 @@
 ist();%0D%0A
+%09
 %09%09q.offe
@@ -896,16 +896,17 @@
 ot);%0D%0A%09%09
+%09
 while (!
@@ -917,24 +917,25 @@
 Empty()) %7B%0D%0A
+%09
 %09%09%09List%3CInte
@@ -981,16 +981,17 @@
 ();%0D%0A%09%09%09
+%09
 int qSiz
@@ -1005,16 +1005,17 @@
 ize();%0D%0A
+%09
 %09%09%09for (
@@ -1048,16 +1048,17 @@
  %7B%0D%0A%09%09%09%09
+%09
 TreeNode
@@ -1072,24 +1072,25 @@
  q.poll();%0D%0A
+%09
 %09%09%09%09thisLeve
@@ -1107,24 +1107,25 @@
 .val);%0D%0A%09%09%09%09
+%09
 if (curr.lef
@@ -1130,32 +1130,33 @@
 eft != null) %7B%0D%0A
+%09
 %09%09%09%09%09q.offer(cur
@@ -1169,19 +1169,21 @@
 );%0D%0A%09%09%09%09
+%09
 %7D%0D%0A
+%09
 %09%09%09%09if (
@@ -1206,24 +1206,25 @@
 ll) %7B%0D%0A%09%09%09%09%09
+%09
 q.offer(curr
@@ -1237,19 +1237,21 @@
 );%0D%0A%09%09%09%09
+%09
 %7D%0D%0A
+%09
 %09%09%09%7D%0D%0A%09%09
@@ -1251,16 +1251,17 @@
 %09%09%7D%0D%0A%09%09%09
+%09
 result.a
@@ -1276,23 +1276,25 @@
 evel);%0D%0A
+%09
 %09%09%7D%0D%0A%09%09
+%09
 Collecti
@@ -1317,83 +1317,11 @@
 lt);
-//this is the only line that gets added/changed to the previous solution.
 %0D%0A
+%09
 %09%09re
@@ -1334,15 +1334,20 @@
 esult;%0D%0A
+%09%09%7D%0D%0A
 %09%7D%0D%0A%7D%0D%0A

refactor 107