107.Binary Tree Level Order Traversal II

题目大意：给出一个二叉树的层序遍历，返回层序遍历按层从底到顶的遍历结果。

法一：层序遍历。一层层的放进list中，待遍历完毕，再从尾到头复制到另一个list中并返回，代码如下（耗时5ms)：

 1 private static List<List<Integer>> levelOrderBottom(TreeNode root) {
 2         if(root == null) {
 3             return new LinkedList<List<Integer>>();
 4         }
 5         List<List<Integer>> listOrder = new LinkedList<List<Integer>>();
 6         Queue<TreeNode> queue = new LinkedList<TreeNode>();
 7         queue.offer(root);
 8         //记录每层的结点个数
 9         int cnt = 1;
10         List<Integer> listLevel = new LinkedList<Integer>();
11         while(!queue.isEmpty()) {
12             TreeNode node = queue.poll();
13             listLevel.add(node.val);
14             cnt--;
15             if(node.left != null) {
16                 queue.offer(node.left);
17             }
18             if(node.right != null) {
19                 queue.offer(node.right);
20             }
21             if(cnt == 0) {
22                 listOrder.add(listLevel);
23                 cnt = queue.size();
24                 listLevel = new LinkedList<Integer>();
25             }
26         }
27         //将list翻转返回
28         List<List<Integer>> listRes = new LinkedList<List<Integer>>();
29         int length = listOrder.size();
30         for(int i = length - 1; i >= 0; i--) {
31             listRes.add(listOrder.get(i));
32         }
33         return listRes;
34     }

View Code

层序遍历的另一种写法，即一层层的一起遍历，看上去是两层循环，其实每个结点只遍历了一遍。list.add(0,in)，将in插入到list的头部。代码如下（耗时2ms）：

 1     private static List<List<Integer>> levelOrderBottom(TreeNode root) {
 2         List<List<Integer>> listOrder = new LinkedList<List<Integer>>();
 3         if(root == null) {
 4             return listOrder;
 5         }
 6         Queue<TreeNode> q = new LinkedList<TreeNode>();
 7         q.offer(root);
 8         while(!q.isEmpty()) {
 9             int len = q.size();
10             List<Integer> listIn = new LinkedList<Integer>();
11             //一层一起遍历
12             for(int i = 0; i < len; i++) {
13                 TreeNode tmp = q.poll();
14                 if(tmp.left != null) {
15                     q.offer(tmp.left);
16                 }
17                 if(tmp.right != null) {
18                     q.offer(tmp.right);
19                 }
20                 listIn.add(tmp.val);
21             }
22             //由于是链表List，所以下面的方法相当于头插，在第0号位置插入元素
23             listOrder.add(0, listIn);
24         }
25         return listOrder;
26     }

View Code

法二：DFS。很特别的一种解法，边遍历结点，边记录结点的深度，采用后序遍历。代码如下（耗时3ms）：

 1     private static List<List<Integer>> levelOrderBottom(TreeNode root) {
 2         List<List<Integer>> res = new LinkedList<List<Integer>>();
 3         levelDFS(res, root, 0);
 4         return res;
 5     }
 6     //后序遍历
 7     private static void levelDFS(List<List<Integer>> list, TreeNode root, int level) {
 8         if(root == null) {
 9             return;
10         }
11         //如果层数大于当前list的大小，则扩充list大小
12         if(level >= list.size()) {
13             list.add(0, new LinkedList<Integer>());
14         }
15         levelDFS(list, root.left, level + 1);
16         levelDFS(list, root.right, level + 1);
17         //由于是倒序输出，所以这里要-level-1，以将倒数几层安排到正数几层进行输出
18         list.get(list.size() - level - 1).add(root.val);
19     }

View Code