《剑指offer》 第32.2题 把二叉树打印成多行

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

刚开始想法是用的print，然后看到题目给的是ArrayList<ArrayList<Integer> >还有点小懵逼。其实是让你返回一个ArrayList，其中每个元素都是一个装了整型数据的ArrayList。比如{[8],[9,10],[11,12,13]}这样的返回方式。比如树有3层，大括号表示的ArrayList就应该装了3个元素。中括号的ArrayList就表示这颗树某一层的所有节点。用这样的方式来区别换行。
另外做本题之前。最好先知道普通版怎么写（不换行打印）。然后在之前的版本上迭代就行。里面有几个点需要注意。在普通版本中，存放元素的ArrayList对象new一个就够了，但本题在返回类型是ArrayList<ArrayList<Integer> >时，不能只new一个，之前分析的有[8],[9,10],[11,12,13]这样的3个ArrayList，因此每while一次（每遍历一层），都需要重新new一个ArrayList存放当前层的所有节点。

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrplus = new ArrayList<ArrayList<Integer>>();
        if(pRoot==null)
            return arrplus; //这里最好返回arrplus而不是null
        Queue<TreeNode> queue = new LinkedList<TreeNode>();      
        queue.offer(pRoot);
        while(!queue.isEmpty()){  
            //这里的arr一定在while里边每次新建一个，因为arr不是复用的。有多个arr
            ArrayList<Integer> arr = new ArrayList<Integer>();
            //这里也要注意，queue的size随时变动，因此进入for循环前拿到这个变量。
            int size = queue.size();        
            for(int i=0;i<size;i++){
                TreeNode temp = queue.poll();
                arr.add(temp.val);
                if(temp.left!=null)
                    queue.offer(temp.left);
                if(temp.right!=null)
                    queue.offer(temp.right);
            }
            arrplus.add(arr);
        }
        return arrplus;
    } 
}

并不是新解法，而是锻炼自己的基本功，将if改成while。

import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrplus = new ArrayList<ArrayList<Integer>>();
        if(pRoot==null)
            return arrplus; //这里最好返回arrplus而不是null
        Queue<TreeNode> queue = new LinkedList<TreeNode>();      
        queue.offer(pRoot);
        while(!queue.isEmpty()){  
            //这里的arr一定在外层的while里边每次新建一个，因为arr不是复用的。有多个arr
            ArrayList<Integer> arr = new ArrayList<Integer>();
            //这里也要注意，queue的size随时变动，因此进入里层while循环前拿到这个变量。
            int size = queue.size();        
            while(size>0){//或者再用一个变量count，赋值为0，每次循环++，相等时结束当前循环
                TreeNode temp = queue.poll();
                arr.add(temp.val);
                if(temp.left!=null)
                    queue.offer(temp.left);
                if(temp.right!=null)
                    queue.offer(temp.right);
               size--;
            }
            arrplus.add(arr);
        }
        return arrplus;
    } 
}

而如果是打印版本，使用print时，区别在于，arr数组变成了一个变量count，用来记录当前层遍历了几个，而size保持不变，依旧是当前层的所有节点，当遍历完后，进入下一轮循环时，输出一个换行符。而里层的循环条件则变成了count == size。只有当前层遍历所有节点时，结束这一层的循环，并在结束前更新size（或者在下一轮循环开始前更新size）。