题解 | #求二叉树的层序遍历#

import java.util.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) throws InterruptedException {
        if(root == null){   //特殊值处理
            return new ArrayList<>(0);
        }
        //创建一个阻塞队列，底层是基于数组实现
        Queue<TreeNode> queue = new ArrayBlockingQueue<TreeNode>(16);
        queue.add(root);  //将根节点压入队列
        int maxInteger = Integer.MAX_VALUE;
        TreeNode wuqg = new TreeNode(maxInteger);  //创建一个标记节点，标记在某一层的最后一个节点
        ArrayList<ArrayList<Integer>> array = new ArrayList<>();  //创建一个二维数组
        ArrayList<Integer> arr = new ArrayList<>();  //创建一个一维数组
        queue.add(wuqg);  //压入标记节点，表示根节点是第一层的最后一个节点
        int count = 0;  //标记量，作为判断结束循环的标记
        while (!queue.isEmpty()){  //当队列中还有元素，继续循环
            // 从队列中拿队首元素，并移除，如果没有则阻塞
            TreeNode node = ((ArrayBlockingQueue<TreeNode>) queue).take();
            if(node.val == maxInteger){  //如果节点的值是maxInteger，则说明是标记节点，其前一节点是某一层的最后一个节点
                count++;  //遍历队列，如果遇到标记节点，count加1，如果count==2，则说明已经遍历完成
                if(count > 1){
                    break;
                }
                ((ArrayBlockingQueue<TreeNode>) queue).put(node);  //压入队列，作为下一层的最后一个节点
                array.add(arr);  //将一维数组压入二维数组
                arr = new ArrayList<>();  //创建一个新的一维数组
            }else{//如果节点的值不是maxInteger，则遍历
                count = 0;  //重新设置为0
                if(node.left != null){   //如果节点的左子节点不为空，入队
                    ((ArrayBlockingQueue<TreeNode>) queue).put(node.left);
                }
                if(node.right != null){   //如果节点的右子节点不为空，入队
                    ((ArrayBlockingQueue<TreeNode>) queue).put(node.right);
                }
                arr.add(node.val);  //加入一维数组
            }
        }
        return array;
    }
}