把二叉树打印成多行

题目描述

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

这道题目与“从上往下打印二叉树”很相似，可以用队列来解决。但是区别在于这道题目需要将每一层进行分行。

解法一：

我们可以使用一个队列来保存当前层的节点，将当前层节点的叶节点保存在另一个队列中，这样需要两个队列来进行遍历。

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> newLine = new ArrayList<Integer>();
        //记录当前层节点
        Queue<TreeNode> list = new LinkedList<TreeNode>();
        //记录当前层的下一层节点
        Queue<TreeNode> nextList = new LinkedList<TreeNode>();
        if(pRoot == null) {
            return res;
        }
        list.add(pRoot);
        //遍历每一层
        while(!list.isEmpty()) {
            newLine = new ArrayList<Integer>();
            while(!list.isEmpty()) {
                TreeNode currentNode = list.poll();
                newLine.add(currentNode.val);
                if(currentNode.left != null) {
                    nextList.add(currentNode.left);
                }
                if(currentNode.right != null) {
                    nextList.add(currentNode.right);
                }
            }
            if(newLine.size() != 0) {
                res.add(newLine);
            } 
            //更新当前层
            list = nextList;
            nextList = new LinkedList<TreeNode>();
        }
        return res;
    }
}

解法二：

实际上我们只需要一个队列也能完成这个任务，只需要记录这个队列中有几个当前层节点，有几个下一层节点。

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(pRoot == null) {
            return res;
        }
        queue.add(pRoot);
        int currentCount = 1;
        int nextCount = 0;
        while(currentCount != 0) {
            ArrayList<Integer> newLine = new ArrayList<Integer>();
            while(currentCount > 0) {
                TreeNode node = queue.poll();
                newLine.add(node.val);
                currentCount--;
                if(node.left != null) {
                    queue.add(node.left);
                    nextCount++;
                }
                if(node.right != null) {
                    queue.add(node.right);
                    nextCount++;
                }
            }
            if(newLine.size() != 0) {
                res.add(newLine);
            }
            currentCount = nextCount;
            nextCount = 0;
        }
        return res;
    }
}

上述代码通过currentCount来记录队列中还剩的当前层节点数，nextCount来记录队列中下一层节点数。

如果一个节点有非空子节点，则每把一个非空子节点放入队列中，nextCount加1。每保存了一个节点，则currentCount减1。

当currentCount为0时，表示当前层打印完毕，接着打印下一层，直到遍历完所有节点。