队列

import java.util.*;
public class Solution {
    //数组模拟队列
    TreeNode q[] = new TreeNode[1510];
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        int hh = 0,tt = 0;
        q[0] = root;
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> ret = new ArrayList<>();
        if(root == null)return res;
        ret.add(1);
        //记录下一层节点的个数
        int nextsum = 0;
        //记录当前层节点的个数
        int cursum = 1;
        while (hh <= tt){
            TreeNode t = q[hh++];
            if(t.left != null){
                q[++tt] = t.left;
                nextsum++;
            }
            if(t.right != null){
                q[++tt] = t.right;
                nextsum++;
            }
            if(cursum - 1 == 0 && nextsum != 0){
                ret.add(nextsum);
                cursum = nextsum;
                nextsum = 0;
            }else if(cursum > 0)cursum--;
        }
        //整理结果集，最后队列里面的数据刚好是按照层来存储的
        int st = 0;
        int len = ret.size();
        for(int i = 0;i < len;i++){
            ArrayList<Integer> list = new ArrayList<>();
            int cut = ret.get(i);
            while (cut > 0){
                list.add(q[st++].val);
                cut--;
            }
            res.add(list);
        }
        return res;
    }
}