1 /**
 2      * Given a binary tree, return the bottom-up level order traversal of its nodes‘ values.
 3      *  (ie, from left to right, level by level from leaf to root).
 4      *  first BSF(but from right to left at each level), then using a stack to traverse from bottom to up
 5      * @param root
 6      * @return
 7      */
 8     public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root){
 9         ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>();
10         if(root == null)
11             return r;
12         // for BFS
13         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
14         // to record the level information
15         LinkedList<Integer> level = new LinkedList<Integer>();
16         //for down to up
17         LinkedList<Integer> stack = new LinkedList<Integer>();
18         //to record the level information of the stack
19         LinkedList<Integer> lel = new LinkedList<Integer>();
20         
21         queue.offer(root);
22         level.offer(1);
23         while(!queue.isEmpty()){
24             TreeNode cur = queue.poll();
25             stack.push(cur.val);// by using stack, we can travesal from the bottom to up
26             int levelCur = level.poll();
27             lel.push(levelCur);
28             if(cur.right!=null)
29             {
30                 queue.offer(cur.right);
31                 level.offer(levelCur+1);
32             }
33             if(cur.left!=null){
34                 queue.offer(cur.left);
35                 level.offer(levelCur+1);
36             }
37         }
38         ArrayList<Integer> al = null;
39         int lev = -1;
40         //from stack to Arraylist
41         while(!stack.isEmpty()){
42             int lc = lel.pop();
43             if(lc!=lev)
44             {
45                 if(al!=null)
46                     r.add(al);
47                 al = new ArrayList<Integer>();
48             }
49             al.add(stack.pop());
50             lev = lc;
51         }
52         r.add(al);
53         return r;
54     }
55 
56 /**
57      * Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).
58      * @param root
59      * @return
60      */
61     public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
62         ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>();
63         if(root == null)
64             return r;
65         //for BFS
66         LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
67         ArrayList<Integer> sub = new ArrayList<Integer>();
68         
69         queue.offer(root);
70         queue.offer(null);// the null node is a label for telling a new level is begin
71         while(!queue.isEmpty()){
72             TreeNode cur = queue.poll();
73             //to see if it is the new level begins
74             if(cur == null){
75                 //a level has finished, we have to put nodes of the level into the total result
76                 r.add(sub);
77                 //begin the next level
78                 if(queue.isEmpty())
79                     break;
80                 else
81                     cur = queue.pop();
82                 queue.offer(null);
83                 //to store the nodes of the new level
84                 sub = new ArrayList<Integer>();
85                 sub.add(cur.val);
86             }else
87                 sub.add(cur.val);
88             
89             if(cur.left!=null)
90                 queue.offer(cur.left);
91             if(cur.right!=null)
92                 queue.offer(cur.right);
93         }
94         return r;
95     }