把二叉树打印成多行

题目描述

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

demo1

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
         //res用来存储每一个arraylist
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
        //arraylist用来存储每一行的数据
        ArrayList<Integer> arraylist = new ArrayList<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(pRoot==null){
            return res;
        }
        //将根节点pRoot入队列
        queue.offer(pRoot);
        //start记录本层打印了多少个，end记录下一层要打印多少个
        int start = 0,end=1;
        while(!queue.isEmpty()){
             //只要队列不为空就执行下面的操作
            //首先将当前节点出队列
            TreeNode treenode = queue.poll();
            //将当前节点的值val添加进arraylist
            arraylist.add(treenode.val);
            //打印的个数加1
            start++;
            //判断是否存在左右节点，并各自入队列
            if(treenode.left!=null){
                queue.offer(treenode.left);
            }
            if(treenode.right!=null){
                queue.offer(treenode.right);
            }
            //当已经打印的个数已经达到该层需要打印的数量时
            if(start==end){
                //重置start和end，end值即为当前queue的容量，也就是下一次需要打印的次数
                start=0;
                end = queue.size();
                //一行打印完成将该行的arraylist添加到res中
                res.add(arraylist);
                //清空arraylist，为添加下一行数据做准备
                arraylist = new ArrayList<Integer>();
            }   
        }
        return res;    
    }  
}

demo2

import java.util.ArrayList;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<TreeNode> treenode = new ArrayList<TreeNode>();
        ArrayList<TreeNode> treenodenew = new ArrayList<TreeNode>();
        ArrayList<Integer> arraylist = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
        if(pRoot==null)
            return res;
        treenode.add(pRoot);//添加第一行的节点
        arraylist.add(pRoot.val);//添加第一行的数据
        res.add(arraylist);//添加第一行的数组
        while(!treenode.isEmpty()){
            arraylist = new ArrayList<Integer>();//清空上一行的arraylist数据
            for(int i=0;i<treenode.size();i++){//遍历每个节点
                if(treenode.get(i).left!=null){//若当前节点存在左节点
                    treenodenew.add(treenode.get(i).left);//将左节点存入新的节点数组
                    arraylist.add(treenode.get(i).left.val);//将左节点数据存入该行的arraylist数组
                }
                if(treenode.get(i).right!=null){//右节点同理
                    treenodenew.add(treenode.get(i).right);
                    arraylist.add(treenode.get(i).right.val);
                }
            }
            treenode.clear();//将上层节点数组清空
            for(int i=0;i<treenodenew.size();i++){//将当前节点数组拷贝至treenode
                treenode.add(treenodenew.get(i));
            }
            //treenode=treenodenew;
            if(!treenodenew.isEmpty())//如果当前节点不为空（有值），就添加进res
                res.add(arraylist);
            treenodenew.clear();//将该层节点清空
        }
       return res;
    }
}