LeetCode hot 热题100 二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) { 
        // 定义一个返回值 `ans`，用于存储按层次遍历的结果。
        // 返回值类型是一个二维数组，其中每一行表示二叉树的某一层节点值。
        
        queue<TreeNode*> q; 
        // 定义一个队列 `q`，用于辅助层次遍历。
        // 队列中存储待处理的节点，先进先出保证按层次依次处理。

        if (root != nullptr) q.push(root); 
        // 如果根节点不为空，将根节点入队，作为遍历的起点。

        vector<vector<int>> ans; 
        // 定义最终结果数组，用于保存每一层的节点值。

        while (!q.empty()) { 
            // 当队列不为空时，表示还有节点需要处理。
            // 逐层遍历二叉树，直到队列为空为止。

            int n = q.size(); 
            // 获取当前队列的大小 `n`，表示当前层节点的数量。

            vector<int> v; 
            // 定义一个临时数组 `v`，用于保存当前层的节点值。

            for (int i = 0; i < n; i++) { 
                // 遍历当前层的所有节点。
                
                TreeNode* node = q.front(); 
                // 取出队首节点进行处理。

                v.push_back(node->val); 
                // 将当前节点的值加入到临时数组 `v` 中。

                q.pop(); 
                // 处理完队首节点后，将其从队列中移除。

                if (node->left) q.push(node->left); 
                // 如果当前节点有左子节点，则将其左子节点加入队列。

                if (node->right) q.push(node->right); 
                // 如果当前节点有右子节点，则将其右子节点加入队列。
            }

            ans.push_back(v); 
            // 将当前层的所有节点值保存到结果数组中。
        }

        return ans; 
        // 返回最终的结果数组。
    }
};

详细思路

1. 目标：

使用层次遍历（Breadth-First Search，BFS）按层收集二叉树中每层的节点值，并将其存储到一个二维数组中。

2. 方法：

使用队列实现 BFS，队列中的每个节点表示待处理的节点。

3. 步骤：

1. 如果树为空（root == nullptr），直接返回空的二维数组。

2. 创建一个队列，并将根节点入队。

3. 进入循环，当队列不为空时：

• 获取当前队列的大小 n，表示当前层的节点数量。

• 遍历 n 个节点：

• 取出队首节点，访问其值并存储到当前层的结果数组中。

• 如果该节点有左子节点，将其左子节点入队。

• 如果该节点有右子节点，将其右子节点入队。

• 将当前层的节点值数组保存到最终结果中。

4. 队列为空时，所有节点已处理完，返回结果数组。

运行过程

假设输入如下二叉树：

         1

       /   \

      2     3

     / \   / \

    4   5 6   7

1. 初始状态：

• 队列：[1]

• 结果：[]

2. 第一层：

• 队列大小：1

• 处理节点：1

• 队列：[2, 3]（将左右子节点 2 和 3 入队）

• 当前层结果：[1]

• 结果：[[1]]

3. 第二层：

• 队列大小：2

• 处理节点：2

• 队列：[3, 4, 5]（将左右子节点 4 和 5 入队）

• 处理节点：3

• 队列：[4, 5, 6, 7]（将左右子节点 6 和 7 入队）

• 当前层结果：[2, 3]

• 结果：[[1], [2, 3]]

4. 第三层：

• 队列大小：4

• 处理节点：4, 5, 6, 7

• 队列：[]（无子节点入队）

• 当前层结果：[4, 5, 6, 7]

• 结果：[[1], [2, 3], [4, 5, 6, 7]]

5. 结束：队列为空，返回结果。

复杂度分析

1. 时间复杂度：

• 每个节点进队和出队一次，总操作次数与节点数量 成正比。

• 时间复杂度：O(n)。

2. 空间复杂度：

• 队列在最坏情况下存储当前层的所有节点，最大值为树的宽度。

• 空间复杂度：O(w)，其中 为二叉树的最大宽度。