二叉树的层序遍历详解

1. 层序遍历基础概念

1.1 什么是层序遍历

层序遍历（Level Order Traversal），也称为广度优先遍历（BFS），是按照二叉树的层次，从上到下、从左到右逐层访问树中每个节点的遍历方式。

1.2 遍历顺序

       3
      / \
     9   20
        /  \
       15   7

层序遍历结果：[3, 9, 20, 15, 7]
第1层：3
第2层：9, 20
第3层：15, 7

1.3 核心思想

层序遍历使用队列数据结构来实现：

1. 将根节点入队
2. 当队列不为空时，出队一个节点并访问
3. 将该节点的左右子节点（如果存在）入队
4. 重复步骤2-3直到队列为空

2. 基础实现

2.1 简单层序遍历

/**
 * 二叉树节点定义
 */
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;
    }
}

/**
 * 基础层序遍历实现
 */
public class LevelOrderTraversal {

    /**
     * 层序遍历 - 返回所有节点值的列表
     * 时间复杂度：O(n)，其中n是节点数量
     * 空间复杂度：O(w)，其中w是二叉树的最大宽度
     */
    public List<Integer> levelOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

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

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);

            // 先左后右入队
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        return result;
    }

    /**
     * 递归实现层序遍历（DFS模拟BFS）
     */
    public List<Integer> levelOrderRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        levelOrderHelper(root, 0, result);
        return result;
    }

    private void levelOrderHelper(TreeNode node, int level, List<Integer> result) {
        if (node == null) {
            return;
        }

        // 确保result有足够的空间
        if (level >= result.size()) {
            result.add(node.val);
        }

        // 递归遍历左右子树
        levelOrderHelper(node.left, level + 1, result);
        levelOrderHelper(node.right, level + 1, result);
    }
}

2.2 分层遍历（按层分组）

/**
 * 按层分组的层序遍历
 * LeetCode 102. Binary Tree Level Order Traversal
 */
public class LevelOrderByLevels {

    /**
     * 返回每一层节点的值
     * 输入: [3,9,20,null,null,15,7]
     * 输出: [[3],[9,20],[15,7]]
     */
    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(); // 当前层的节点数量
            List<Integer> currentLevel = new ArrayList<>();

            // 处理当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                // 将下一层的节点加入队列
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(currentLevel);
        }

        return result;
    }

    /**
     * 递归实现分层遍历
     */
    public List<List<Integer>> levelOrderRecursive(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        levelOrderHelper(root, 0, result);
        return result;
    }

    private void levelOrderHelper(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) {
            return;
        }

        // 如果这是新的一层，创建新的列表
        if (level >= result.size()) {
            result.add(new ArrayList<>());
        }

        // 将当前节点值添加到对应层
        result.get(level).add(node.val);

        // 递归处理下一层
        levelOrderHelper(node.left, level + 1, result);
        levelOrderHelper(node.right, level + 1, result);
    }
}

3. 层序遍历变体问题

3.1 自底向上的层序遍历

/**
 * LeetCode 107. Binary Tree Level Order Traversal II
 * 自底向上的层序遍历
 */
public class LevelOrderBottom {

    /**
     * 从最底层开始返回层序遍历结果
     * 输入: [3,9,20,null,null,15,7]
     * 输出: [[15,7],[9,20],[3]]
     */
    public List<List<Integer>> levelOrderBottom(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();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

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

            // 在列表开头插入，实现自底向上
            result.add(0, currentLevel);
        }

        return result;
    }

    /**
     * 优化版本：先正常遍历，最后反转
     */
    public List<List<Integer>> levelOrderBottomOptimized(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();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

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

            result.add(currentLevel);
        }

        // 最后反转整个结果
        Collections.reverse(result);
        return result;
    }
}

3.2 锯齿形层序遍历

/**
 * LeetCode 103. Binary Tree Zigzag Level Order Traversal
 * 锯齿形（之字形）层序遍历
 */
public class ZigzagLevelOrder {

    /**
     * 奇数层从左到右，偶数层从右到左
     * 输入: [3,9,20,null,null,15,7]
     * 输出: [[3],[20,9],[15,7]]
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToRight = true; // 控制遍历方向

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                if (leftToRight) {
                    currentLevel.add(node.val);
                } else {
                    // 从右到左，在列表开头插入
                    currentLevel.add(0, node.val);
                }

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

            result.add(currentLevel);
            leftToRight = !leftToRight; // 切换方向
        }

        return result;
    }

    /**
     * 使用双端队列优化版本
     */
    public List<List<Integer>> zigzagLevelOrderDeque(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            Deque<Integer> currentLevel = new LinkedList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                if (leftToRight) {
                    currentLevel.offerLast(node.val);
                } else {
                    currentLevel.offerFirst(node.val);
                }

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

            result.add(new ArrayList<>(currentLevel));
            leftToRight = !leftToRight;
        }

        return result;
    }
}

3.3 每层的最大值

/**
 * LeetCode 515. Find Largest Value in Each Tree Row
 * 在每个树行中找最大值
 */
public class FindLargestValueInEachRow {

    /**
     * 找到每一层的最大值
     * 输入: [1,3,2,5,3,null,9]
     * 输出: [1,3,9]
     */
    public List<Integer> largestValues(TreeNode root) {
        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();
            int maxVal = Integer.MIN_VALUE;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                maxVal = Math.max(maxVal, node.val);

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

            result.add(maxVal);
        }

        return result;
    }

    /**
     * 递归实现
     */
    public List<Integer> largestValuesRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        largestValuesHelper(root, 0, result);
        return result;
    }

    private void largestValuesHelper(TreeNode node, int level, List<Integer> result) {
        if (node == null) {
            return;
        }

        if (level >= result.size()) {
            result.add(node.val);
        } else {
            result.set(level, Math.max(result.get(level), node.val));
        }

        largestValuesHelper(node.left, level + 1, result);
        largestValuesHelper(node.right, level + 1, result);
    }
}

3.4 二叉树的右视图

/**
 * LeetCode 199. Binary Tree Right Side View
 * 二叉树的右视图
 */
public class RightSideView {

    /**
     * 返回从右侧观察二叉树能看到的节点值
     * 输入: [1,2,3,null,5,null,4]
     * 输出: [1,3,4]
     */
    public List<Integer> rightSideView(TreeNode root) {
        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();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                // 如果是这一层的最后一个节点，加入结果
                if (i == levelSize - 1) {
                    result.add(node.val);
                }

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

        return result;
    }

    /**
     * 递归实现 - 先访问右子树
     */
    public List<Integer> rightSideViewRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        rightSideViewHelper(root, 0, result);
        return result;
    }

    private void rightSideViewHelper(TreeNode node, int level, List<Integer> result) {
        if (node == null) {
            return;
        }

        // 如果这是新的一层，添加第一个遇到的节点（右侧）
        if (level >= result.size()) {
            result.add(node.val);
        }

        // 先遍历右子树，再遍历左子树
        rightSideViewHelper(node.right, level + 1, result);
        rightSideViewHelper(node.left, level + 1, result);
    }
}

4. 高级应用

4.1 完全二叉树的节点个数

/**
 * LeetCode 222. Count Complete Tree Nodes
 * 完全二叉树的节点个数
 */
public class CountCompleteTreeNodes {

    /**
     * 计算完全二叉树的节点个数
     * 时间复杂度：O(log²n)
     * 空间复杂度：O(logn)
     */
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 计算左子树和右子树的高度
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        if (leftHeight == rightHeight) {
            // 左子树是满二叉树
            return (1 << leftHeight) + countNodes(root.right);
        } else {
            // 右子树是满二叉树
            return (1 << rightHeight) + countNodes(root.left);
        }
    }

    private int getHeight(TreeNode node) {
        int height = 0;
        while (node != null) {
            height++;
            node = node.left; // 完全二叉树最左侧路径就是高度
        }
        return height;
    }

    /**
     * 二分查找解法
     */
    public int countNodesBinarySearch(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int height = getHeight(root);
        if (height == 1) {
            return 1;
        }

        // 二分查找最后一层的节点数
        int left = 0, right = (1 << (height - 1)) - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (exists(root, height, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return (1 << (height - 1)) - 1 + left; // 前面的满二叉树 + 最后一层的节点数
    }

    private boolean exists(TreeNode root, int height, int index) {
        int left = 0, right = (1 << (height - 1)) - 1;

        for (int i = 0; i < height - 1; i++) {
            int mid = left + (right - left) / 2;
            if (index <= mid) {
                root = root.left;
                right = mid;
            } else {
                root = root.right;
                left = mid + 1;
            }
        }

        return root != null;
    }
}

4.2 层序遍历构建二叉树

/**
 * 从层序遍历结果构建二叉树
 */
public class BuildTreeFromLevelOrder {

    /**
     * 从完整的层序遍历数组构建二叉树
     * 输入: [3,9,20,null,null,15,7]
     */
    public TreeNode buildTree(Integer[] levelOrder) {
        if (levelOrder == null || levelOrder.length == 0 || levelOrder[0] == null) {
            return null;
        }

        TreeNode root = new TreeNode(levelOrder[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int index = 1;
        while (!queue.isEmpty() && index < levelOrder.length) {
            TreeNode node = queue.poll();

            // 处理左子节点
            if (index < levelOrder.length && levelOrder[index] != null) {
                node.left = new TreeNode(levelOrder[index]);
                queue.offer(node.left);
            }
            index++;

            // 处理右子节点
            if (index < levelOrder.length && levelOrder[index] != null) {
                node.right = new TreeNode(levelOrder[index]);
                queue.offer(node.right);
            }
            index++;
        }

        return root;
    }

    /**
     * 从字符串构建二叉树
     * 输入: "3,9,20,null,null,15,7"
     */
    public TreeNode buildTreeFromString(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }

        String[] values = data.split(",");
        return buildTree(parseValues(values));
    }

    private Integer[] parseValues(String[] values) {
        Integer[] result = new Integer[values.length];
        for (int i = 0; i < values.length; i++) {
            result[i] = "null".equals(values[i]) ? null : Integer.parseInt(values[i]);
        }
        return result;
    }

    /**
     * 将二叉树序列化为层序遍历字符串
     */
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        List<String> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            if (node != null) {
                result.add(String.valueOf(node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                result.add("null");
            }
        }

        // 移除末尾的null
        while (!result.isEmpty() && "null".equals(result.get(result.size() - 1))) {
            result.remove(result.size() - 1);
        }

        return String.join(",", result);
    }
}

4.3 二叉树的层平均值

/**
 * LeetCode 637. Average of Levels in Binary Tree
 * 二叉树的层平均值
 */
public class AverageOfLevels {

    /**
     * 计算每一层的平均值
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            long sum = 0; // 使用long避免溢出

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                sum += node.val;

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

            result.add((double) sum / levelSize);
        }

        return result;
    }

    /**
     * 递归实现
     */
    public List<Double> averageOfLevelsRecursive(TreeNode root) {
        List<Long> sums = new ArrayList<>();
        List<Integer> counts = new ArrayList<>();

        averageHelper(root, 0, sums, counts);

        List<Double> result = new ArrayList<>();
        for (int i = 0; i < sums.size(); i++) {
            result.add((double) sums.get(i) / counts.get(i));
        }

        return result;
    }

    private void averageHelper(TreeNode node, int level, List<Long> sums, List<Integer> counts) {
        if (node == null) {
            return;
        }

        if (level >= sums.size()) {
            sums.add(0L);
            counts.add(0);
        }

        sums.set(level, sums.get(level) + node.val);
        counts.set(level, counts.get(level) + 1);

        averageHelper(node.left, level + 1, sums, counts);
        averageHelper(node.right, level + 1, sums, counts);
    }
}

5. 性能优化技巧

5.1 内存优化

/**
 * 内存优化的层序遍历
 */
public class MemoryOptimizedLevelOrder {

    /**
     * 使用两个列表交替存储，减少队列内存占用
     */
    public List<List<Integer>> levelOrderOptimized(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        List<TreeNode> currentLevel = new ArrayList<>();
        currentLevel.add(root);

        while (!currentLevel.isEmpty()) {
            List<Integer> values = new ArrayList<>();
            List<TreeNode> nextLevel = new ArrayList<>();

            for (TreeNode node : currentLevel) {
                values.add(node.val);

                if (node.left != null) {
                    nextLevel.add(node.left);
                }
                if (node.right != null) {
                    nextLevel.add(node.right);
                }
            }

            result.add(values);
            currentLevel = nextLevel;
        }

        return result;
    }

    /**
     * 只保存值，不保存节点引用
     */
    public List<Integer> levelOrderValuesOnly(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>(); // ArrayDeque比LinkedList更高效
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);

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

        return result;
    }
}

5.2 并行处理

/**
 * 并行层序遍历（适用于大型二叉树）
 */
public class ParallelLevelOrder {

    /**
     * 使用CompletableFuture并行处理
     */
    public List<List<Integer>> parallelLevelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = Collections.synchronizedList(new ArrayList<>());
        ExecutorService executor = ForkJoinPool.commonPool();

        processLevelParallel(Arrays.asList(root), 0, result, executor);

        return result;
    }

    private void processLevelParallel(List<TreeNode> currentLevel, int level,
                                    List<List<Integer>> result, ExecutorService executor) {
        if (currentLevel.isEmpty()) {
            return;
        }

        // 确保result有足够的大小
        synchronized (result) {
            while (result.size() <= level) {
                result.add(new ArrayList<>());
            }
        }

        List<CompletableFuture<Void>> futures = new ArrayList<>();
        List<TreeNode> nextLevel = Collections.synchronizedList(new ArrayList<>());

        // 并行处理当前层的每个节点
        for (TreeNode node : currentLevel) {
            CompletableFuture<Void> future = CompletableFuture.runAsync(() -> {
                // 添加节点值到结果
                synchronized (result.get(level)) {
                    result.get(level).add(node.val);
                }

                // 收集下一层的节点
                if (node.left != null) {
                    nextLevel.add(node.left);
                }
                if (node.right != null) {
                    nextLevel.add(node.right);
                }
            }, executor);

            futures.add(future);
        }

        // 等待当前层处理完成
        CompletableFuture.allOf(futures.toArray(new CompletableFuture[0])).join();

        // 递归处理下一层
        processLevelParallel(nextLevel, level + 1, result, executor);
    }

    /**
     * 使用ForkJoinTask实现
     */
    static class LevelOrderTask extends RecursiveTask<List<List<Integer>>> {
        private final TreeNode root;

        public LevelOrderTask(TreeNode root) {
            this.root = root;
        }

        @Override
        protected List<List<Integer>> compute() {
            if (root == null) {
                return new ArrayList<>();
            }

            List<List<Integer>> result = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);

            while (!queue.isEmpty()) {
                int levelSize = queue.size();
                List<Integer> currentLevel = new ArrayList<>();

                // 如果当前层节点数量足够大，考虑并行处理
                if (levelSize > 100) {
                    List<CompletableFuture<Integer>> futures = new ArrayList<>();

                    for (int i = 0; i < levelSize; i++) {
                        TreeNode node = queue.poll();

                        CompletableFuture<Integer> future = CompletableFuture.supplyAsync(() -> {
                            if (node.left != null) {
                                synchronized (queue) {
                                    queue.offer(node.left);
                                }
                            }
                            if (node.right != null) {
                                synchronized (queue) {
                                    queue.offer(node.right);
                                }
                            }
                            return node.val;
                        });

                        futures.add(future);
                    }

                    // 收集结果
                    for (CompletableFuture<Integer> future : futures) {
                        currentLevel.add(future.join());
                    }
                } else {
                    // 节点数较少，使用串行处理
                    for (int i = 0; i < levelSize; i++) {
                        TreeNode node = queue.poll();
                        currentLevel.add(node.val);

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

                result.add(currentLevel);
            }

            return result;
        }
    }
}

6. 实际应用场景

6.1 文件系统遍历

/**
 * 文件系统的层序遍历
 */
public class FileSystemTraversal {

    static class FileNode {
        String name;
        boolean isDirectory;
        List<FileNode> children;
        long size;

        public FileNode(String name, boolean isDirectory) {
            this.name = name;
            this.isDirectory = isDirectory;
            this.children = new ArrayList<>();
        }
    }

    /**
     * 按层打印文件系统结构
     */
    public void printFileSystemByLevel(FileNode root) {
        if (root == null) {
            return;
        }

        Queue<FileNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            System.out.println("Level " + level + ":");

            for (int i = 0; i < levelSize; i++) {
                FileNode node = queue.poll();
                String prefix = "  ".repeat(level);
                String type = node.isDirectory ? "DIR" : "FILE";

                System.out.println(prefix + "- " + node.name + " (" + type + ")");

                if (node.isDirectory && node.children != null) {
                    for (FileNode child : node.children) {
                        queue.offer(child);
                    }
                }
            }

            level++;
            System.out.println();
        }
    }

    /**
     * 计算每层的文件大小总和
     */
    public List<Long> calculateLevelSizes(FileNode root) {
        List<Long> levelSizes = new ArrayList<>();
        if (root == null) {
            return levelSizes;
        }

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

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            long totalSize = 0;

            for (int i = 0; i < levelSize; i++) {
                FileNode node = queue.poll();

                if (!node.isDirectory) {
                    totalSize += node.size;
                }

                if (node.children != null) {
                    for (FileNode child : node.children) {
                        queue.offer(child);
                    }
                }
            }

            levelSizes.add(totalSize);
        }

        return levelSizes;
    }
}

6.2 组织架构遍历

/**
 * 组织架构的层序遍历
 */
public class OrganizationTraversal {

    static class Employee {
        String name;
        String position;
        List<Employee> subordinates;
        int level;

        public Employee(String name, String position) {
            this.name = name;
            this.position = position;
            this.subordinates = new ArrayList<>();
        }
    }

    /**
     * 按管理层级打印组织架构
     */
    public void printOrganizationChart(Employee ceo) {
        if (ceo == null) {
            return;
        }

        Queue<Employee> queue = new LinkedList<>();
        ceo.level = 0;
        queue.offer(ceo);

        Map<Integer, List<Employee>> levelMap = new HashMap<>();

        while (!queue.isEmpty()) {
            Employee employee = queue.poll();

            levelMap.computeIfAbsent(employee.level, k -> new ArrayList<>()).add(employee);

            for (Employee subordinate : employee.subordinates) {
                subordinate.level = employee.level + 1;
                queue.offer(subordinate);
            }
        }

        // 按层级打印
        for (int level : levelMap.keySet()) {
            System.out.println("Management Level " + level + ":");
            for (Employee emp : levelMap.get(level)) {
                String indent = "  ".repeat(level);
                System.out.println(indent + "- " + emp.name + " (" + emp.position + ")");
            }
            System.out.println();
        }
    }

    /**
     * 统计每个管理层级的人数
     */
    public Map<Integer, Integer> countEmployeesByLevel(Employee ceo) {
        Map<Integer, Integer> levelCounts = new HashMap<>();
        if (ceo == null) {
            return levelCounts;
        }

        Queue<Employee> queue = new LinkedList<>();
        ceo.level = 0;
        queue.offer(ceo);

        while (!queue.isEmpty()) {
            Employee employee = queue.poll();

            levelCounts.put(employee.level,
                           levelCounts.getOrDefault(employee.level, 0) + 1);

            for (Employee subordinate : employee.subordinates) {
                subordinate.level = employee.level + 1;
                queue.offer(subordinate);
            }
        }

        return levelCounts;
    }
}

7. 复杂度分析

7.1 时间复杂度

操作	时间复杂度	说明
基础层序遍历	O(n)	每个节点访问一次
分层遍历	O(n)	每个节点访问一次
锯齿形遍历	O(n)	每个节点访问一次
构建树	O(n)	每个节点创建一次

7.2 空间复杂度

操作	空间复杂度	说明
队列空间	O(w)	w为树的最大宽度
结果存储	O(n)	存储所有节点值
递归栈	O(h)	h为树的高度

7.3 最坏情况分析

/**
 * 不同树形状的复杂度分析
 */
public class ComplexityAnalysis {

    /**
     * 完全二叉树：最优情况
     * 高度：O(log n)
     * 最大宽度：O(n/2) = O(n)
     */
    public void analyzeCompleteBinaryTree() {
        // 高度为h的完全二叉树
        // 节点数：2^h - 1
        // 最后一层最多有：2^(h-1)个节点
        // 队列最大长度：2^(h-1) = O(n/2)
    }

    /**
     * 链式树：最坏情况
     * 高度：O(n)
     * 最大宽度：O(1)
     */
    public void analyzeLinkedTree() {
        // 退化为链表的二叉树
        // 高度：n
        // 每层只有1个节点
        // 队列最大长度：1
    }

    /**
     * 满二叉树：平衡情况
     * 高度：O(log n)
     * 最大宽度：O(n/2)
     */
    public void analyzeFullBinaryTree() {
        // 每层都满的二叉树
        // 最后一层有一半的节点
        // 队列最大长度约为n/2
    }
}

8. 调试和测试

8.1 可视化调试

/**
 * 层序遍历的可视化调试工具
 */
public class LevelOrderDebugger {

    /**
     * 打印层序遍历的详细过程
     */
    public void debugLevelOrder(TreeNode root) {
        if (root == null) {
            System.out.println("Empty tree");
            return;
        }

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

        System.out.println("Level Order Traversal Debug:");
        System.out.println("============================");

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            System.out.printf("Level %d (size: %d): ", level, levelSize);

            List<TreeNode> currentLevel = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node);
                System.out.print(node.val + " ");

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

            System.out.println();

            // 打印子节点信息
            for (TreeNode node : currentLevel) {
                System.out.printf("  Node %d: left=%s, right=%s%n",
                                node.val,
                                node.left != null ? node.left.val : "null",
                                node.right != null ? node.right.val : "null");
            }

            System.out.printf("  Queue after level %d: [", level);
            queue.forEach(node -> System.out.print(node.val + " "));
            System.out.println("]");
            System.out.println();

            level++;
        }
    }

    /**
     * 验证层序遍历结果
     */
    public boolean verifyLevelOrder(TreeNode root, List<List<Integer>> expected) {
        List<List<Integer>> actual = new LevelOrderByLevels().levelOrder(root);

        if (actual.size() != expected.size()) {
            System.out.printf("Level count mismatch: expected %d, got %d%n",
                            expected.size(), actual.size());
            return false;
        }

        for (int i = 0; i < expected.size(); i++) {
            if (!actual.get(i).equals(expected.get(i))) {
                System.out.printf("Level %d mismatch: expected %s, got %s%n",
                                i, expected.get(i), actual.get(i));
                return false;
            }
        }

        System.out.println("Level order traversal verified successfully!");
        return true;
    }
}

8.2 性能测试

/**
 * 层序遍历性能测试
 */
public class LevelOrderPerformanceTest {

    /**
     * 测试不同算法的性能
     */
    public void benchmarkAlgorithms() {
        // 生成测试数据
        TreeNode[] testTrees = generateTestTrees();

        System.out.println("Performance Benchmark");
        System.out.println("====================");

        for (int i = 0; i < testTrees.length; i++) {
            TreeNode tree = testTrees[i];
            int nodeCount = countNodes(tree);

            System.out.printf("%nTest Case %d (nodes: %d):%n", i + 1, nodeCount);

            // 测试迭代版本
            long startTime = System.nanoTime();
            new LevelOrderByLevels().levelOrder(tree);
            long iterativeTime = System.nanoTime() - startTime;

            // 测试递归版本
            startTime = System.nanoTime();
            new LevelOrderByLevels().levelOrderRecursive(tree);
            long recursiveTime = System.nanoTime() - startTime;

            System.out.printf("  Iterative: %.2f μs%n", iterativeTime / 1000.0);
            System.out.printf("  Recursive: %.2f μs%n", recursiveTime / 1000.0);
            System.out.printf("  Ratio: %.2fx%n", (double) recursiveTime / iterativeTime);
        }
    }

    private TreeNode[] generateTestTrees() {
        return new TreeNode[] {
            generateCompleteBinaryTree(15),     // 完全二叉树
            generateLinkedTree(15),             // 链式树
            generateRandomTree(15),             // 随机树
            generateBalancedTree(15)            // 平衡树
        };
    }

    private TreeNode generateCompleteBinaryTree(int n) {
        if (n <= 0) return null;

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

        int val = 2;
        while (!queue.isEmpty() && val <= n) {
            TreeNode node = queue.poll();

            if (val <= n) {
                node.left = new TreeNode(val++);
                queue.offer(node.left);
            }

            if (val <= n) {
                node.right = new TreeNode(val++);
                queue.offer(node.right);
            }
        }

        return root;
    }

    private TreeNode generateLinkedTree(int n) {
        if (n <= 0) return null;

        TreeNode root = new TreeNode(1);
        TreeNode current = root;

        for (int i = 2; i <= n; i++) {
            current.left = new TreeNode(i);
            current = current.left;
        }

        return root;
    }

    private TreeNode generateRandomTree(int n) {
        // 简化实现：生成随机结构的树
        if (n <= 0) return null;

        Random random = new Random(42); // 固定种子保证可重复
        TreeNode root = new TreeNode(1);

        // 使用随机方式构建树（简化版本）
        return root;
    }

    private TreeNode generateBalancedTree(int n) {
        return generateBalancedTreeHelper(1, n);
    }

    private TreeNode generateBalancedTreeHelper(int start, int end) {
        if (start > end) return null;

        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(mid);

        root.left = generateBalancedTreeHelper(start, mid - 1);
        root.right = generateBalancedTreeHelper(mid + 1, end);

        return root;
    }

    private int countNodes(TreeNode root) {
        if (root == null) return 0;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

9. 总结

9.1 核心要点

1. 基本思想：使用队列实现逐层访问
2. 时间复杂度：O(n)，每个节点访问一次
3. 空间复杂度：O(w)，w为树的最大宽度
4. 适用场景：需要按层处理的树形结构问题

9.2 常见变体

• 分层遍历：返回每层节点的分组结果
• 锯齿形遍历：奇偶层交替改变遍历方向
• 自底向上：从叶子层开始向根层遍历
• 右视图：每层最右侧的节点

9.3 实践建议

1. 选择合适的数据结构：队列（LinkedList/ArrayDeque）
2. 注意边界条件：空树、单节点树
3. 考虑内存优化：大型树可能需要优化内存使用
4. 递归vs迭代：一般推荐迭代方式，更直观且避免栈溢出

9.4 扩展应用

层序遍历不仅适用于二叉树，还可以应用于：

• 多叉树遍历
• 图的广度优先搜索
• 文件系统遍历
• 组织架构分析
• 网络拓扑分析

掌握层序遍历是解决树相关问题的重要基础，通过理解其原理和各种变体，可以灵活应对各种实际问题。