【算法】队列+bfs算法 解决树的相关算法题(C++)

发布时间:2024年01月18日

1. 前言

队列 宽度优先算法(BFS)是解决很多算法问题的常见工具。

BFS通过逐层遍历图或树的节点来寻找解决问题的最短路径或最短步骤。使用队列可以很好地支持BFS算法的实现。

下面是一个使用队列和宽度优先算法解决问题的一般步骤:

  1. 创建一个空队列,并将起始节点放入队列中。
  2. 创建一个集合用于记录已经访问过的节点,防止重复访问。(visited数组,一般用于路径、迷宫问题)
  3. 初始化其他必要的辅助数据结构,例如距离数组或状态数组等。
  4. 开始循环,直到队列为空:
    • 从队列中取出一个节点作为当前节点。
    • 如果当前节点是目标节点,说明找到了解,结束搜索。
    • 否则,将当前节点的所有未访问过的邻居节点加入队列,并将这些节点标记为已访问。
  5. 如果需要记录路径或其他信息,可以在搜索过程中相应地更新辅助数据结构。
  6. 如果队列为空,说明不存在解。

使用队列和宽度优先算法可以解决许多问题,例如迷宫问题、最短路径问题、连通性问题等。具体的实现方式可能因问题而异,但基本思路是相似的。


2. 算法题

429.N叉树的层序遍历

在这里插入图片描述

思路

  • 解法队列,宽度优先搜索
    在这里插入图片描述

    1. 如上图所写,首先将根节点入队
    2. 循环队列,直至队列为空:
      3. q.size即为该层节点数,循环q.size次:提取出队头节点,并将该节点的所有子节点入队
    3. 每遍历一层,将结果加入到结果数组ret中

代码

vector<vector<int>> levelOrder(Node* root) {
    vector<vector<int>> ret; // 最终结果
    queue<Node*> q; // 用队列记录节点
    // 将本层元素放入队列,提取出值后出队,将子节点入队
    if(root) q.push(root);
    else    return ret;
    while(q.size())
    {
        int sz = q.size(); // 记录本层元素个数
        vector<int> tmp; // 用于存储本层元素值
        for(int i = 0; i < sz; ++i)
        {
            Node* t = q.front();
            q.pop();
            tmp.push_back(t->val); // tmp记录该层节点值
            for(Node* child : t->children) // 当前节点的子节点入队
            {
                if(child) // 不为空
                    q.push(child);
            }
        }
        ret.push_back(tmp); // 更新结果
    }
    return ret;
}

103.二叉树的锯齿形层序遍历

在这里插入图片描述

思路

  • 题意分析:要求按照先从左往右进行一层遍历、再从左往右进行下一层遍历,重复遍历完二叉树
    • 我们可以将其理解为奇数层正序遍历(从左向右),偶数层逆序遍历
  • 解法队列,宽度优先搜索
  • 该题与上一道很类似,只需要添加一个遍历用于标记当前层为奇数还是偶数,用于判断逆序还是正序
    1. 使用一个队列来存储当前层的所有节点,同时记录当前层的节点数。
    2. 依次从队列中取出节点,将其值加入到当前层的结果集tmp中,并将其左右子节点加入队列中。
    3. 如果当前层为偶数层,则需要将tmp逆序后再加入到结果集ret中。
    4. 最后返回结果集ret。

代码

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    // 锯齿形层序遍历:偶数层逆序遍历,奇数层正常遍历
    vector<vector<int>> ret;
    queue<TreeNode*> q;
    if(!root) return ret;
    else q.push(root);
    int level = 1; // 根据flag判断是否逆序
    while(q.size())
    {
        int sz = q.size(); // 记录本层个数
        vector<int> tmp;
        for(int i = 0; i < sz; ++i)
        {
            TreeNode* t = q.front();
            q.pop();
            tmp.push_back(t->val);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        if(level % 2 == 0)   reverse(tmp.begin(), tmp.end());
        ret.push_back(tmp);
        ++level;
    }
    
    return ret;
}

662.二叉树最大宽度

在这里插入图片描述

思路

  • 题意分析:即返回二叉树的最大宽度,即最大层的宽度
  • 解法:记录节点下标、数组表示队列
    在这里插入图片描述
    • 如上图的思路,我们用数组表示队列,队列中存放pair类型,分别为节点和其对应的下标
    1. 将根节点及其下标1插入队列,进行循环,直至队列为空
    2. 提取队尾和队头两元素(即为该层的最左最有的节点)并记录 / 更新结果
    3. 将该层的所有子节点入队
    4. 最后返回结果ret

代码

int widthOfBinaryTree(TreeNode* root) {
    // 队列(数组)存储节点及其下标(补全null节点后的下标)
    vector<pair<TreeNode*, unsigned int>> q;
    // q.push_back(make_pair<nullptr, 0>); 
    if(!root) return 0;
    else q.push_back({root, 1}); // // 根节点从1下标开始
    unsigned int ret = 0; // 最终结果

    while(q.size())
    {
        // 计算本层宽度
        auto [node1, x1] = q[0]; // 提取一个pair类型
        auto [node2, x2] = q.back();
        ret = max(ret, x2 - x1 + 1);

        vector<pair<TreeNode*, unsigned int>> tmp; // tmp存储下一层节点信息,覆盖q
        for(auto& [node, x] : q)
        {
            // 左孩子下标:2x 右孩子下标:2x+1
            if(node->left) tmp.push_back({node->left, 2*x});
            if(node->right) tmp.push_back({node->right, 2*x + 1});
        }

        q = tmp;
    }
    return ret;
}

515.在每个树行中找最大值

在这里插入图片描述

思路

  • 解法队列 + 层序遍历
  • 直接利用队列队树进行层序遍历即可
  • 每层循环定义一次变量maxVal用于寻找最大值

代码

vector<int> largestValues(TreeNode* root) {
    vector<int> ret; // 结果数组
    queue<TreeNode*> q; // 队列用于层序遍历
    if(!root) return ret;
    else q.push(root);
    
    while(!q.empty())
    {
        int sz = q.size();
        int maxVal = INT_MIN; // 用于比较节点大小 
        while(sz--)
        {
            auto t = q.front(); // 提取当前节点
            q.pop();
            maxVal = max(maxVal, t->val);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        ret.push_back(maxVal);
    }

    return ret;
}
文章来源:https://blog.csdn.net/Dreaming_TI/article/details/135651984
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。