【面试题60-把二叉树打印成多行】

剑指offer第六十题。

题目描述

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

解题思路

一开始我以为就是简单的层序遍历嘛：

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        
        if(pRoot == null){
            return res;
        }
        
        LinkedList<TreeNode> queue = new LinkedList<>();
        
        queue.add(pRoot);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.pop();
            ArrayList<Integer> list = new ArrayList<>();
            list.add(node.val);
           
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
            
            if(list.size() != 0){
                res.add(list);
            }
        }
        
        return res;
    }
    
}

然后结果是：

用例:
{8,6,10,5,7,9,11}

对应输出应该为:

[[8],[6,10],[5,7,9,11]]

你的输出为:

[[8],[6],[10],[5],[7],[9],[11]]

事实上，这里需要将在同一层的数放到一个集合之中，所以还需要加工一下才行。

我的答案

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        
        if(pRoot == null){
            return res;
        }
        
        LinkedList<TreeNode> queue = new LinkedList<>();
        
        queue.add(pRoot);
        
        //先把root放进结果集
        ArrayList<Integer> list = new ArrayList<>();
        list.add(pRoot.val);
        res.add(list);
        
        while(!queue.isEmpty()){
            //统计一下当前队列中的个数，因为当前队列中存放的都是同一层的数据
            //所以需要对这一层进行处理
            int num = queue.size();
            list = new ArrayList<>();
            while(num > 0){
                TreeNode node = queue.pop();
                if(node.left != null){
                    list.add(node.left.val);
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                    list.add(node.right.val);
                }
                num--;
            }
            if(list.size() != 0){
                res.add(list);
            }
        }
        return res;
    }
    
}