本文共 1624 字，大约阅读时间需要 5 分钟。

剑指 Offer 32 - II. 从上到下打印二叉树 II

题目要求实现一个函数，按照层序遍历的方式打印二叉树的节点值，每一层的节点按从左到右的顺序打印，并且每一层的节点值组成一个列表，所有层的列表组成最终的输出。

解题思路

该问题可以通过广度优先搜索（BFS）算法来解决。BFS算法使用队列来实现，能够按层遍历二叉树。具体步骤如下：

解决代码

import java.util.ArrayList;import java.util.LinkedList;import java.util.List;class TreeNode {    int val;    TreeNode left;    TreeNode right;    public TreeNode(int val) {        this.val = val;        this.left = null;        this.right = null;    }}public class Solution {    public List
   
    
     > levelOrder(TreeNode root) {        List
     
      
       > res = new ArrayList<>();        if (root == null) {            return res;        }        LinkedList
       
         queue = new LinkedList<>();        queue.add(root);        while (!queue.isEmpty()) {            int levelSize = queue.size();            List
        
          levelList = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); levelList.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } res.add(levelList); } return res; }}
        
       
      
     
    
   

代码解释

• TreeNode 类：定义了二叉树的节点结构，包含节点值、左孩子和右孩子。
• levelOrder 方法：实现了从上到下按层打印二叉树的功能。
  • 初始化：检查根节点是否为空，若为空返回空列表。否则，初始化队列，并将根节点加入队列。
  • 循环处理：当队列不为空时，处理当前层的所有节点。创建临时列表存储当前层的节点值，并将每个节点的左孩子和右孩子加入队列。
  • 结果处理：将当前层的节点值列表添加到结果列表中。
• 返回：最终返回结果列表，包含每一层的节点值列表。

该算法的时间复杂度为 O(N)，其中 N 是二叉树的节点总数。空间复杂度为 O(N)，最坏情况下（如平衡二叉树），队列中最多同时存储 N/2 个节点。