剑指offer11

题目描述

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

解题思路

其实这道题多了一个每一层输出一行，我相信要是直接在一行输出的话，大家都知道怎么在一行输出，用一个队列就可以实现，但是多了一个每一层输出一行的条件之后，其实也不麻烦，我们只需要在输出的打印的时候知道每层有多少个节点就好了，就可以解决换行输出这个问题了

代码实现

public ArrayList<ArrayList<Integer>> print(TreeNode pRoot) {
    if (pRoot == null) {
        return null;
    }
    ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>(); 
    queue.offer(pRoot);
    //声明两个用于记录整数，start用来记录这一层已经访问了几个节点了，end用于记录当前层的所有节点数
    int start = 0, end = 1;
    ArrayList<Integer> list = new ArrayList<Integer>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.remove();
        list.add(node.val);
        // 访问过的节点数+1
        start++;
        // 正在访问的节点的左孩子入队列（如果不为空的话）
        if (node.left != null) {
            queue.offer(node.left);
        }
        //正在访问的节点的右孩子入队列（如果不为空的话）
        if (node.right != null) {
            queue.offer(node.right);
        }
        //判断是否该层的节点全访问了没有
        if (start == end) {
            //从新开始计数下一层的访问个数
            start = 0;
            //下一层的节点个数
            end = queue.size();
            lists.add(list);
            list = new ArrayList<Integer>();
        }
    }
    return lists;
}