102 二叉树的层序遍历

    3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

public List<List<Integer>> levelOrder(TreeNode root) {
    //定义结果集
    List<List<Integer>> result = new ArrayList<>();
    //根节点为空
    if(root = null) return result;
    //实现队列(也可以用别的LinkedList快一点)
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while(!queue.isEmpty()){
        //每一层的遍历
        List<Integer> level = new ArrayList<Integer>();
        int size = queue.size();
        for(int i = 0; i < size; i++){
            TreeNode node = queue.poll();
            level.add(node);
            if(node.left != null) queue.offer(node.left);
            if(node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

public List<List<Integer>> levelOrder(TreeNode root) {
    //结果集
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(root == null) return result;
    dfs(1,root,result);
    return result;
} 
public void dfs(int level, TreeNode root, List<List<Integer>> result) {
    //容器大小小于层级则添加一个新层级
    if(result.size()<level) {
        result.add(new ArrayList<Integer>());
    }
    //往对应的层级List添加值
    result.get(level - 1).add(root.val);
    //往下面走，层级+1
    if(root.left!=null) {
        dfs(level+1, root.left, result);
    }
    if(root.right!=null) {
        dfs(level+1, root.right, result);
    }
}