【剑指offer】-把二叉树打印成多行-43/67

1. 题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

2. 题目分析

1. 非常经典的一道二叉树的题目，做这道题之前需要掌握二叉树的思想和BFS(广度优先搜索、队列思想)
2. 我们可以回顾一下最基本的层次遍历，我们是用一个队列来进行存储初始root结点，然后依次放入root的左子树和右子树，循环上述操作

while (!queue.isEmpty()) {
			TreeNode treeNode = queue.poll();
			if (treeNode.left != null) {
				queue.add(treeNode.left);
			}
			if (treeNode.right != null) {
				queue.add(treeNode.right);
			}
		}

3. 对于这道题，我们需要分层，所以我们需要考虑，怎么让一层的数字输出在同一list中，当我们把root放入队列时，目前的队列长度为1，我们按照队列的长度来进行循环queue.add(treeNode.left); queue.add(treeNode.right);，目前队列中的长度为2，我们继续按照队列的长度进行循环，依次来遍历还整个二叉树。

3. 题目代码

public class Solution {
  ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (pRoot == null) {
            return list;
        }
        queue.offer(pRoot);
        while (!queue.isEmpty()) {
            ArrayList<Integer> list2 = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode treeNode = queue.poll();
                list2.add(treeNode.val);
                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
            }
            list.add(list2);
        }
        return list;
  }
}