1、解题思路

层序遍历是一种广度优先搜索（BFS）的应用。我们可以使用队列来辅助实现层序遍历：

  1. 将根节点放入队列。
  2. 遍历当前队列中的所有节点，并将它们的值存入当前层的列表中。
  3. 将这些节点的子节点（从左到右）依次加入队列。
  4. 重复上述过程，直到队列为空。

2、代码实现

C++
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> result;
        if (root == nullptr) {
            return result;
        }

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();   // 当前层数的节点数量
            vector<int> curLevel;

            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                curLevel.push_back(node->val);

                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }

            result.push_back(curLevel);
        }

        return result;
    }
};
Python
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
from typing import List, Optional
from collections import deque

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        result = []
        if not root:
            return result
        
        queue = deque([root])
        
        while queue:
            levelSize = len(queue)  # 当前层的节点数量
            currentLevel = []
            
            for _ in range(levelSize):
                node = queue.popleft()
                currentLevel.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(currentLevel)
        
        return result

3、复杂度分析

  • 时间复杂度：O(n)，每个节点被访问一次。
  • 空间复杂度：O(n)，队列中最多存储 n 个节点。