Binary Tree Level Order Traversal II

 1 public class Solution {
 2     public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 6         if(root == null)
 7             return result;
 8         Stack<ArrayList<Integer>> stack = new Stack<ArrayList<Integer>>();
 9         stack = traversal(root);
10         while(!stack.isEmpty())
11             result.add(stack.pop());
12         return result;
13     }
14     private Stack<ArrayList<Integer>> traversal(TreeNode root)
15     {
16         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
17         Stack<ArrayList<Integer>> result = new Stack<ArrayList<Integer>>();
18         queue.add(root);
19         while(!queue.isEmpty())
20         {
21             ArrayList<Integer> tmp = new ArrayList<Integer>();
22             LinkedList<TreeNode> tmpqueue = new LinkedList<TreeNode>();
23             while(!queue.isEmpty())
24             {
25                 TreeNode node = queue.poll();
26                 tmp.add(node.val);
27                 if(node.left != null)
28                     tmpqueue.add(node.left);
29                 if(node.right != null)
30                     tmpqueue.add(node.right);
31             }
32             result.add(tmp);
33             queue = tmpqueue;
34         }
35         return result;
36     }
37 }