1. 标记每层最右结点

1.1 分析

辅助队列
last记录本层最右结点，nLast记录下层最右结点（入队时标记）。出队到last时本层输出完，last更新为nLast。

1.2 代码

import java.util.*
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(pRoot == null) return res;
        TreeNode last = pRoot;
        TreeNode nLast = null;
        q.offer(pRoot);
        while(!q.isEmpty()){
            //出队，加入本层数组
            TreeNode node = q.poll();
            list.add(node.val);
            //左右孩子入队
            //nLast 记录最新入队的结点，用于标记本层最右结点
            if(node.left!=null){
                q.offer(node.left);
                nLast = node.left;
            }
            if(node.right!=null){
                q.offer(node.right);
                nLast = node.right;
            }
            //本层结点出队完毕，本层数组加入二维数组，last更新为nLast
            if(node == last ){//最后一层出队后，q空，但还需要加入数组
                res.add(list);
                list = new ArrayList<>();
                last = nLast;
            }
        }
        return res;
    }

1.3 复杂度

空间：O(n)
时间：O(n)

2. 每层结点计数

2.1 分析

辅助队列
thislevel和nextLevel代表当前和下一层结点数

2.2 代码

import java.util.*
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(pRoot == null) return res;
        int thisLevel = 1;
        int nextLevel = 0;
        q.offer(pRoot);
        while(!q.isEmpty()){
            //出队，加入本层数组
            TreeNode node = q.poll();
            list.add(node.val);
            thisLevel--;
            //左右孩子入队
            if(node.left!=null){
                q.offer(node.left);
                nextLevel++;
            }
            if(node.right!=null){
                q.offer(node.right);
                nextLevel++;
            }
            //本层结点出队完毕，本层数组加入二维数组
            if(thisLevel == 0 ){
                res.add(list);
                list = new ArrayList<>();
                thisLevel = nextLevel;
                nextLevel = 0;
            }
        }
        return res;
    }
}

2.3 复杂度

同1