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

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * bfs:先把这一层的结点遍历完
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        
        // 核心武器：队列
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);  // 根结点入队

        while (queue.size() != 0) {
            int currentLevelSize = queue.size();  //存储当前层级的结点数，不然后面出不了循环
            ArrayList<Integer> currentLevelList = new ArrayList<>();

            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode currentNode = queue.poll();  //出队一个
                currentLevelList.add(currentNode.val);

                // 把它的下一代（左右孩子）接到队尾，留到下一轮 while 循环处理
                if (currentNode.left != null) queue.offer(currentNode.left);
                if (currentNode.right != null) queue.offer(currentNode.right);

            }

            res.add(currentLevelList);
        }

        return res;
    }
}