JZ60：把二叉树打印成多行

解法1：增加两个TreeNode：last和nlast

• last：表示当前遍历层最右结点
• nlast：表示下一层最右结点

遍历时，每次将nlast指向插入队列元素，最后一个插入结点时即最右结点。插入左右孩子之后，检测last是否为当前输出结点，若是，则表示需要进行换行，并将last指向下一层的nlast。

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
        if(pRoot==null){
            return list;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(pRoot);
        TreeNode last=pRoot;
        TreeNode nlast=pRoot;
        ArrayList<Integer> res=new ArrayList<Integer>();
        while(!queue.isEmpty()){
            TreeNode tmp=queue.poll();
            res.add(tmp.val);

            if(tmp.left!=null){
                queue.add(tmp.left);
                nlast=tmp.left;
            }
            if(tmp.right!=null){
                queue.add(tmp.right);
                nlast=tmp.right;
            }
            if(tmp==last){
                list.add(res);
                last=nlast;
                res=new ArrayList<Integer>();
            }
        }
        return list;
    }

}

解法2：根据层次遍历的顺序，每一层都是从左到右的遍历输出，借助于一个队列。

先将根节点入队，当前节点是队头节点，将其出队并访问，如果当前节点的左节点不为空将左节点入队，如果当前节点的右节点不为空将其入队。所以出队顺序也是从左到右依次出队。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
         ArrayList<ArrayList<Integer>> result = new ArrayList<>();
         if (root == null) {
            return result;
        }
         Queue<TreeNode> queue = new LinkedList<>();
         queue.add(root);
         while(!queue.isEmpty()) {
             ArrayList<Integer> list = new ArrayList<>();
             int size = queue.size();
             for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                list.add(temp.val);
                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
            }
             //result.add(0,list);
             result.add(list);
         }
         return result;
    }
}