20. 二叉树的层次遍历：从上到下按层打印二叉树，每一层打印到一行

PangHu大约 2 分钟

要从上到下按层打印二叉树，并且每一层打印到一行，我们可以使用广度优先搜索（BFS）来遍历二叉树。通常，广度优先搜索使用队列来实现。为了能够按层打印，每遍历完一层，我们可以记录这一层的所有节点，然后再开始处理下一层的节点。

1. 算法思路

使用队列进行广度优先搜索：将根节点放入队列，然后逐层遍历二叉树。
记录当前层的节点数量：每次处理队列中的节点时，记录当前层的节点数，然后逐个将它们的子节点（如果有）加入队列。
分层打印：在处理完当前层的所有节点后，将这一层的节点值打印到一行。

2. 代码实现

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
        left = null;
        right = null;
    }
}

public class LevelOrderTraversal {

    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 currentNode = queue.poll();
                currentLevel.add(currentNode.val);

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

            result.add(currentLevel);
        }

        return result;
    }

    public static void main(String[] args) {
        LevelOrderTraversal solution = new LevelOrderTraversal();

        // 构造一个二叉树：
        //      3
        //     / \
        //    9  20
        //      /  \
        //     15   7
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        List<List<Integer>> result = solution.levelOrder(root);
        for (List<Integer> level : result) {
            System.out.println(level);
        }
    }
}

3. 示例解释

假设我们有以下二叉树：

按照上述代码的流程，层次遍历的结果将是：

[3]
[9, 20]
[15, 7]

4. 复杂度分析

时间复杂度：O(n)，其中 n 是二叉树中的节点数。每个节点在遍历时被访问一次。
空间复杂度：O(n)，最坏情况下，队列中可能包含二叉树的所有节点。

5. 总结

通过使用队列进行广度优先搜索，我们可以有效地按层遍历二叉树，并将每一层的节点值分行输出。这种方法简单高效，广泛应用于树的层次遍历问题中。