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

算法流程：
1、特殊情况：如果树的根节点为空，则直接返回 【】
2、初始化：返回列表 res ，辅助栈 stack
3、层次遍历循环 当栈为空跳出：
    1、新建列表tmp，用于临时存储当前层打印结果
    2、当前层打印循环：循环次数为当前层节点数量
        1、出栈：栈底元素，记为 node
        2、打印：将所在层节点值添加到 tmp中
        3、添加子节点：若 node 的左右子树不为空，则 入栈

    3、将tmp添加到res中
4、返回打印结果 res

图解：

Python版本

class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        # bfs
        res = []
        if not pRoot:
            return res
        stack = [pRoot]
        while stack:
            tmp = []
            for i in range(len(stack)):
                # 获取栈中第一个元素
                node = stack[0]
                # 去除栈中第一个元素
                stack = stack[1:]
                tmp.append(node.val)
                if node.left:
                    # 栈中添加左子树
                    stack.append(node.left)
                if node.right:
                    # 栈中添加右子树
                    stack.append(node.right)
            # 将每层节点添加到res
            res.append(tmp)
        return res

复杂度分析：

时间复杂度：N为二叉树的节点数量，层次遍历二叉树、进出栈
空间复杂度： 最差情况下，即当树为满二叉树时，最多有 N/2 个树节点 同时 在 stack 中，使用 大小的额外空间。

I. 按层打印： 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。
II. 每层打印到一行： 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

算法流程:

1、特例处理： 当根节点为空，则返回空列表 [] ；
2、初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] ；
3、BFS 循环： 当队列 queue 为空时跳出；
    1、新建一个临时列表 tmp ，用于存储当前层打印结果；
    2、当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）；
        1、出队： 队首元素出队，记为 node；
        2、打印： 将 node.val 添加至 tmp 尾部；
        3、添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
    3、将当前层结果 tmp 添加入 res 。
4、返回值： 返回打印结果列表 res 即可。
图解：

该图解和方法一图解相似则参考上图，差别在于此方法使用双端队列存储二叉树结点

JAVA版本

import java.util.*;


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

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if(pRoot!=null) deque.add(pRoot);
         
        while(!deque.isEmpty()){
            ArrayList<Integer> tmp = new ArrayList<>();
            for(int i = deque.size(); i>0; i--){
                // 队列中第一个元素
                TreeNode node = deque.removeFirst();
                tmp.add(node.val);
                // 左右子树入队列
                if(node.left!=null) deque.add(node.left);
                if(node.right!=null) deque.add(node.right);
            }
            res.add(tmp);
        }
        return res;
    }
     
}

复杂度分析：

时间复杂度：N为二叉树的节点数量，层次遍历二叉树
空间复杂度： 最差情况下，即当树为满二叉树时，最多有 N/2 个树节点 同时 在 queue 中，使用 大小的额外空间。