【二叉树】Leetcode 102. 二叉树的层序遍历【中等】

二叉树的层序遍历

二叉树的层序遍历 是广度优先搜索（BFS）的一种特殊情况，也称为宽度优先遍。

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）

示例1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

解题思路

层序遍历是一种按层次逐层遍历二叉树节点的方法，通常使用队列来实现。

• 1、创建一个队列，用于存储待访问的节点。
• 2、将根节点加入队列。
• 3、循环遍历队列，直到队列为空：
  弹出队首节点，并将其值加入到结果列表中。
  如果当前节点有左子节点，则将左子节点加入队列。
  如果当前节点有右子节点，则将右子节点加入队列。
• 4、返回结果列表。

java实现

public class LevelOrderTraversal {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            //当前层的节点数量
            int levelSize = queue.size();
            //存储当前层的节点的levelNodes
            List<Integer> levelNodes = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                //出队
                TreeNode current = queue.poll();
                //添加到对应层级的list中
                levelNodes.add(current.val);

                //利用栈的先进先出（FIFO）
                //对应测试案例的入栈后顺序为：3、9、20、5、15、17
                if (current.left != null) {
                    queue.offer(current.left);
                }

                if (current.right != null) {
                    queue.offer(current.right);
                }
            }

            result.add(levelNodes);
        }

        return result;
    }

    public static void main(String[] args) {
        // 构造一个二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(5);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        // 创建 LevelOrderTraversal 对象
        LevelOrderTraversal solution = new LevelOrderTraversal();

        // 进行层序遍历
        List<List<Integer>> result = solution.levelOrder(root);

        // 打印结果
        System.out.println("Level Order Traversal: " + result);
    }
}

时间空间复杂度

• 时间复杂度：O(n)，其中n是二叉树中的节点数，每个节点都需要访问一次。
• 空间复杂度：O(n)，最坏情况下需要存储所有节点的值。