当前位置：首页 > article >正文

二叉树层序遍历 Leetcode102.二叉树的层序遍历

article 2025/1/14 17:58:22

二叉树的层序遍历相当于图论的广度优先搜索，用队列来实现

（二叉树的递归遍历相当于图论的深度优先搜索）

102.二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

思路解析

层序遍历的核心思想
- 层序遍历（或广度优先搜索，BFS）是通过逐层访问节点来遍历树。
- 通常利用 队列（queue） 数据结构完成，每次处理一层的所有节点，然后将下一层的节点加入队列。
算法步骤
1. 特殊情况处理：
  - 如果树为空（root == nullptr），直接返回空的二维数组。
2. 初始化队列：
  - 创建一个队列 que，将根节点 root 入队。
3. 逐层遍历：
  - 每次记录当前队列的大小（size），代表当前层的节点数量。
  - 遍历这一层的节点，依次从队列中取出节点，存入当前层的结果数组（vec）。
  - 如果节点有左子节点或右子节点，将其加入队列，作为下一层要访问的节点。
4. 记录结果：
  - 将当前层的结果数组 vec 添加到最终结果数组 result 中。
5. 重复上述过程，直到队列为空。
6. 返回结果：
  - 最终返回存储每一层节点值的二维数组 result。

que 是一个存储 TreeNode* 类型的队列

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result; // 用于存储最终的层序遍历结果
        if (root == nullptr) return result; // 如果根节点为空，返回空的结果

        queue<TreeNode*> que; // 队列用于辅助层序遍历
        que.push(root); // 将根节点加入队列

        while (!que.empty()) {
            int size = que.size(); // 当前层的节点数量
            vector<int> vec; // 用于存储当前层的节点值

            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front(); // 取出队首节点
                que.pop(); // 弹出队首节点

                vec.push_back(node->val); // 存储当前节点的值

                // 将左子节点加入队列
                if (node->left) {
                    que.push(node->left);
                }

                // 将右子节点加入队列
                if (node->right) {
                    que.push(node->right);
                }
            }

            result.push_back(vec); // 将当前层的节点值存入结果中
        }

        return result; // 返回最终结果
    }
};

107.二叉树的层序遍历||

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

思路：我们可以先进行标准的层序遍历，然后将结果逆序。

只需在return result前多加一个 reverse(result.begin(), result.end());

199.二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

输入：root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

思路：就是其他的元素都不存入，只存入一行中最右边的那个元素

 if (i == size - 1) {
                    result.push_back(node->val);
                }

所以最后的result就不是二维数组，而是一维数组来存入元素

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result; // 用于存储右视图的节点值
        if (root == nullptr) return result; // 如果树为空，直接返回空的结果

        queue<TreeNode*> que; // 队列用于辅助层序遍历
        que.push(root); // 根节点入队

        while (!que.empty()) {
            int size = que.size(); // 当前层的节点数量

            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front(); // 获取队首节点
                que.pop(); // 弹出队首节点

                // 如果是当前层的最后一个节点，存入结果
                if (i == size - 1) {
                    result.push_back(node->val);
                }

                // 左子节点入队
                if (node->left) {
                    que.push(node->left);
                }

                // 右子节点入队
                if (node->right) {
                    que.push(node->right);
                }
            }
        }

        return result; // 返回右视图结果
    }
};

637.二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

只需要增加计算每层平均数的功能即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
         vector<double> result; // 用于存储最终的层序遍历结果
        if (root == nullptr) return result; // 如果根节点为空，返回空的结果
        double arg=0;
        queue<TreeNode*> que; // 队列用于辅助层序遍历
        que.push(root); // 将根节点加入队列

        while (!que.empty()) {
            int size = que.size(); // 当前层的节点数量
            vector<int> vec; // 用于存储当前层的节点值

            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front(); // 取出队首节点
                que.pop(); // 弹出队首节点
               arg+=node->val;
                // 将左子节点加入队列
                if (node->left) {
                    que.push(node->left);
                }

                // 将右子节点加入队列
                if (node->right) {
                    que.push(node->right);
                }
                
            }
            result.push_back(arg/size); // 将当前层的节点值存入结果中
            arg=0;
        }

        return result; // 返回最终结果 
    }
};