求二叉树的层序遍历

1.dfs(广度遍历)
利用一个队列就可以实现，时间复杂度，空间复杂度均为O（n）
import java.util.*;

/*

• public class TreeNode {
• int val = 0;
• TreeNode left = null;
• TreeNode right = null;
• }
• /

public class Solution {
/*
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<integer>> res=new ArrayList<>();
if(root==null)//树为空
return res;
Queue<treenode> q=new LinkedList<>();
q.offer(root);//添加根结点
while(!q.isEmpty()){
ArrayList<integer> temp=new ArrayList<>();//用于存每一层的数字的集合
int size=q.size();//每一层有多少个数字
for(int i=0;i<size;i++){//遍历出队列中的数字作为一组
TreeNode t=q.poll();
temp.add(t.val);
if(t.left!=null){//添加左结点
q.offer(t.left);
}
if(t.right!=null){//添加右结点
q.offer(t.right);
}
}
res.add(temp);
}
return res;
}
}
2.递归实现（中序遍历，DFS深度遍历）
因为每一层的深度都是一样的，我们可以用每一层的深度作为一个索引，进行添加每一层的数字，时间复杂度，空间复杂度均为O（n）
import java.util.</integer></treenode></integer></integer>;

/*

• public class TreeNode {
• int val = 0;
• TreeNode left = null;
• TreeNode right = null;
• }
• /

public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<integer>> res=new ArrayList<>();
if(root==null)//树为空
return res;
DFS(root,res,0);//深度遍历
return res;
}
public void DFS(TreeNode root,ArrayList<ArrayList<integer>> list,int depth){
if(root==null)//结点为空
return;
if(depth==list.size())
list.add(new ArrayList<integer>());
DFS(root.left,list,depth+1);//遍历左子树
list.get(depth).add(root.val);//根结点
DFS(root.right,list,depth+1);//遍历右子树
}
}</integer></integer></integer></integer>