Binary Tree Level Order Traversal II
https://leetcode.com/problems/binary-tree-level-order-traversal-ii
Same as Binary Tree Level Order Traversal
The only difference is up side down. So use a stack for output.
Source code Read on Github
1 /**
2 * Definition for binary tree
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10 public class Solution {
11 public List<List<Integer>> levelOrderBottom(TreeNode root) {
12 LinkedList<List<Integer>> rt = new LinkedList<List<Integer>>();
13
14 if(root == null) return rt;
15
16 final TreeNode END = new TreeNode(0);
17
18 Deque<TreeNode> queue = new LinkedList<TreeNode>();
19
20 queue.add(root);
21 queue.add(END);
22
23 ArrayList<Integer> level = new ArrayList<Integer>();
24
25 while(!queue.isEmpty()){
26
27 TreeNode node = queue.poll();
28
29 if(node == END){
30 rt.push(new ArrayList<Integer>(level)); // copy
31 level.clear();
32
33 if(!queue.isEmpty()) queue.add(END);
34
35 }else{
36
37 level.add(node.val);
38
39 if(node.left != null) queue.addLast(node.left);
40 if(node.right != null) queue.addLast(node.right);
41 }
42 }
43
44 return rt;
45 }
46 }