二叉树的层序遍历

原题链接

使用的方法

• Queue.add(): 将元素添加到队列的尾部，如果队列已满，则抛出 IllegalStateException。
• Queue.poll(): 从队列的头部获取并移除元素，如果队列为空，则返回 null。
• Queue.size(): 返回队列中元素的数量。

解题思路

• BFS（广度优先搜索）
• 层序遍历是指按照树的层次从上到下、从左到右依次访问树的节点。
• 我们可以使用一个队列来实现层序遍历。首先将根节点加入队列，然后进入循环，直到队列为空。
• 在每次循环中，我们记录当前队列的大小，这个大小代表了当前层的节点数量。我们创建一个新的列表来存储当前层的节点值。
• 接着，我们使用一个循环来处理当前层的所有节点。在这个循环中，我们从队列中取出一个节点，将其值添加到当前层的列表中，并将它的左子节点和右子节点（如果存在）加入队列。
• 当处理完当前层的所有节点后，我们将当前层的列表添加到结果列表中。最后返回结果列表。

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root != null)
            queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}