如何实现二叉树的层次遍历算法？

二叉树的层次遍历(Level Order Traversal)问题是按层遍历一棵二叉树。我们可以使用队列实现二叉树的层次遍历算法:

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 size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode curr = queue.poll();
            level.add(curr.val);
            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
        }
        result.add(level);
    }

    return result;
}

算法流程:

1. 定义result存储结果,queue用于层次遍历。
2. 根节点入队列。
3. while循环,当队列非空时继续遍历。size记录当前层节点数。
4. 遍历当前层所有节点,将节点的值加入level,并将左右节点入队列。
5. 当前层遍历完成,将level加入result。
6. 重复3-5,直至遍历完所有节点,返回result。
7. 特殊情况,root为空,返回result。

时间复杂度O(n),空间复杂度O(n)。

所以,二叉树层次遍历的关键是:

1. 使用队列记录每一层的节点。
2. 遍历当前层所有节点,将节点值加入结果,并将左右子节点入队列。
3. 当前层遍历完成,将本层结果加入最终结果。
4. 重复以上步骤,直到队列为空,得到最终结果。