二叉树：按层输出

    给定一个二叉树，要求从下往上输出每层的元素值。如以下二叉树，则输出的结果为[[15,7],[9,20],[3]]。

    按照二叉树的搜索策略，有宽度优先搜索和深度优先搜索两种方法。

    一、宽度优先搜索方法BFS：把二叉树的节点装进队列里，利用队列先进先出的特点，来按层级的顺序遍历二叉树。这种方法访问顺序与题目要求的输出一致，更为简洁。

  public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> result = new LinkedList<List<Integer>>();if(root == null)return result;LinkedList<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while(!queue.isEmpty()) {List<Integer> subList = new LinkedList<Integer>();int levelSize = queue.size();    //记录每层的元素个数，每层建立一个subListfor(int i = 0; i < levelSize; i++) {    //按层循环，循环次数为每层的元素个数TreeNode node = queue.poll();    //访问完后从队列删除，保证queue.size()等于每层的元素个数if(node.left != null) queue.offer(node.left);if(node.right != null) queue.offer(node.right);subList.add(node.val);   }result.add(0,subList);    //第一个参数为index，从链表头插入}return result;}

    二、深度优先搜索方法DFS：使用递归算法，把层级数作为参数传递，根据层级数把节点加入到相应的列表中。

   public List<List<Integer>> levelOrderBottom(TreeNode root) {LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();if(root == null)return result;BFS(root, 1, result);Collections.reverse(result);    //要求的结果为BFS返回值的倒序return result;}public void BFS(TreeNode root, int level, LinkedList<List<Integer>> list) {if(root == null)    //到达叶子节点，直接返回return;if(list.size() < level) {    //采用先序遍历，如果list.size<level，说明是该层的第一个节点，需新建一个subListList<Integer> subList = new LinkedList<Integer>();list.add(subList);}list.get(level -1).add(root.val);if(root.left != null) BFS(root.left, level + 1, list);   if(root.right != null) BFS(root.right, level + 1, list);}