题解 | #把二叉树打印成多行#

广度优先、深度优先（JAVA实现）
层序遍历叫宽度优先(bfs),通常可以使用bfs实现的都可以使用dfs实现

思路一：bfs 时间O(N),每个节点遍历一次，空间O(N),树的宽度

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(pRoot==null)
            return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        while(queue.size()>0)
        {
            int len=queue.size();
            ArrayList<Integer> tempList = new ArrayList<>();
            while(len>0)
            {
                TreeNode node=queue.poll();
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
                tempList.add(node.val);
                len--;
            }
            list.add(tempList);
        }
        return list;
    }
}

思路二：dfs 时间O(N),每个节点遍历一次，空间O(N),树的深度，最坏退化链表，最好树为平衡二叉树，log(N)

public class Solution {
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        dfs(pRoot,0);
        return list;
    }
    private void dfs(TreeNode root,int level)
    {
        if(root==null)
            return;
        if(list.size()<=level)
        {
            list.add(new ArrayList());//当前深度大于等于列表的长度，需要新建一个子列表
        }
        list.get(level).add(root.val);
        dfs(root.left,level+1);
        dfs(root.right,level+1);
    }
}