LeetCode题：107. 二叉树的层次遍历II
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其自底向上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
迭代实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<>();
if(root == null) return res;
queue.add(root);
while(!queue.isEmpty()){
int cur = queue.size();
ArrayList<Integer> tmp = new ArrayList<Integer>();
for(int i=0;i<cur;i++){
TreeNode t= queue.poll();
tmp.add(t.val);
if(t.left != null)
queue.add(t.left);
if(t.right != null)
queue.add(t.right);
}
res.add(tmp);
}
return res;
}
}
广度优先遍历是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用广度优先来做非常合适。
广度优先需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。在这里插入图片描述
首先拿出根节点，如果左子树/右子树不为空，就将他们放入队列中。第一遍处理完后，根节点已经从队列中拿走了，而根节点的两个孩子已放入队列中了，现在队列中就有两个节点 2 和 5。
第二次处理，会将 2 和 5 这两个节点从队列中拿走，然后再将 2 和 5 的子节点放入队列中，现在队列中就有三个节点 3，4，6。
我们把每层遍历到的节点都放入到一个结果集中，最后返回这个结果集就可以了。
时间复杂度： O(n)O(n)
空间复杂度：O(n)O(n)
递归实现（深度优先搜索）
用广度优先处理是很直观的，可以想象成是一把刀横着切割了每一层，但是深度优先遍历就不那么直观了。
我们开下脑洞，把这个二叉树的样子调整一下，摆成一个田字形的样子。田字形的每一层就对应一个 list。
按照深度优先的处理顺序，会先访问节点 1，再访问节点 2，接着是节点 3。之后是第二列的 4 和 5，最后是第三列的 6。
每次递归的时候都需要带一个 index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的 list 不存在，就加入一个空 list 进去。
动态演示如下：
时间复杂度：O(N)O(N)
空间复杂度：O(h)O(h)，h 是树的高度
代码如下
import java.util.*;
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) {
return new ArrayList<List<Integer>>();
}
//用来存放最终结果
List<List<Integer>> res = new ArrayList<List<Integer>>();
dfs(1,root,res);
return res;
}
void dfs(int index,TreeNode root, List<List<Integer>> res) {
//假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
if(res.size()<index) {
res.add(new ArrayList<Integer>());
}
//将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
//res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
res.get(index-1).add(root.val);
//递归的处理左子树，右子树，同时将层数index+1
if(root.left!=null) {
dfs(index+1, root.left, res);
}
if(root.right!=null) {
dfs(index+1, root.right, res);
}
}
}