算法笔记（十）——队列＋宽搜

时间：2024-10-06 14:29:44

文章目录

  • N 叉数的层序遍历
  • 二叉树的锯齿形层序遍历
  • 二叉树最大宽度
  • 在每个树行中找最大值

BFS是图上最基础、最重要的搜索算法之一；
每次都尝试访问同一层的节点如果同一层都访问完了，再访问下一层

BFS基本框架

void bfs(起始点)
{
	将起始点放入队列中;
	标记起点已访问;
	while(队列不为空)
	{
		访问队列中首元素;
		删除队首元素;
		for(队首元素所有相邻点)
		{
			if(该点未被访问过且合法)
				将该点加入队列末尾; 
		}
	}
	宽搜结束; 
}

N 叉数的层序遍历

题目：N 叉数的层序遍历

在这里插入图片描述
思路

  • BFS（宽搜）
  • 创建vector<vector<int>> ret来保存结果；
  • 创建queue<Node*> q来将根节点入队，如果根节点为空则直接返回空的ret
  • 当队列不为空的时候一直循环：
    • 获取当前队列大小
    • 用vector<int> tmp来统计本层节点
    • 出队头元素，保存在tmp中，若其孩子节点非空，则进入队列
    • 每层节点出队后，将其保存在tmp中的节点，push_back进ret

C++代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution 
{
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        vector<vector<int>> ret; // 存储层序遍历的结果
        queue<Node*> q; // 层序遍历需要的队列

        if(root == nullptr) return ret;

        q.push(root);
        while(q.size())
        {
            int n = q.size(); // 本层元素个数
            vector<int> tmp;  // 统计本层节点
            for(int i = 0; i < n; i++)
            {
                Node* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                for(Node* child : t->children) // 让下一次节点入队
                {
                    if(child != nullptr)
                        q.push(child);
                }
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

二叉树的锯齿形层序遍历

题目：二叉树的锯齿形层序遍历

在这里插入图片描述
思路1

  • 和上一题的思路一样，我们先封装一个函数vector<vector<int>> levelOrder(TreeNode *root)正常层序遍历该二叉树，将其结果存储在vector<vector<int>> ret
  • 再对结果ret进行逆序，当为偶数层时，对其结果进行逆序；

C++代码

/**
 * 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<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int>> ret = levelOrder(root);
        // 偶数层时，对其结果进行逆序
        for (int i = 1; i < ret.size(); i += 2)
            reverse(ret[i].begin(), ret[i].end());
        return ret;
    }

    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> ret;
        if (!root)
            return ret;
        queue<TreeNode* > q;
        q.push(root);

        while (q.size())
        {
            int n = q.size();
            vector<int> tmp;
            for(int i = 0; i < n; i++)
            {
                TreeNode* t = q.front();
                tmp.push_back(t->val);
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};

思路2
我们也可以添加一个标记位flag，当奇数层时，正常添加到结果数组，偶数层时，逆序后进入结果数组

C++代码

/**
 * 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<vector<int>> zigzagLevelOrder(TreeNode *root)
    {
        vector<vector<int>> ret;
        if (!root)
            return ret;
        queue<TreeNode* > q;
        q.push(root);
        int flag = 0; // 标志层数

        while (q.size())
        {
            flag++;
            int n = q.size();
            vector<int> tmp;
            for(int i = 0; i < n; i++)
            {
                TreeNode* t = q.front();
                tmp.push_back(t->val);
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            if(flag % 2 == 0) reverse(tmp.begin(), tmp.end()); // 偶数层逆序后再进入结果数组
            ret.push_back(tmp);
        }
        return ret;
    }

};

二叉树最大宽度

题目：二叉树最大宽度

在这里插入图片描述

思路
对于数组存储的二叉树，我们知道

  • 父亲节点下标为i（从一开始）。则，
  • 左孩子下标为2 * i
  • 左孩子下标为2 * i + 1

如果二叉树非常不平衡，节点全部在右侧，空节点也进行插入操作去计算的话，空间是远远不够的

  • 我们可以通过计算每层插入节点的头和尾下标差值，并使用vector来模拟队列操作
  • 每次都覆盖前一层，以防超出内存
  • 计算差值，使用无符号整型，避免数据溢出
  • 定义一个队列 vector<pair<TreeNode*, unsigned int>> q；// 数组模拟队列，元素包含一个二叉树节点指针和该节点在完全二叉树中的编号
  • 将根节点和其对应编号 1 放入队列 q中
  • 进入循环，获取当前层数收尾元素，并且更新当前最大宽度
  • 创建一个临时队列tmp来更新q

C++代码

/**
 * 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:
    int widthOfBinaryTree(TreeNode* root) 
    {
        vector<pair<TreeNode*, unsigned int>> q; // 数组模拟队列
        q.push_back({root, 1});
        unsigned int ret = 0;

        while(q.size())
        {
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            ret = max(ret, y2 - y1 + 1);

            // 下一层进临时队
            vector<pair<TreeNode*, unsigned int>> tmp;
            for(auto& [x, y] : q)
            {
                if(x->left) tmp.push_back({x->left, y * 2});
                if(x->right) tmp.push_back({x->right, y * 2 + 1});
            }
            q = tmp;
        }    

        return ret;
    }
};

在每个树行中找最大值

题目：在每个树行中找最大值

在这里插入图片描述

思路

利用层序遍历，统计每层最大值；

C++代码

/**
 * 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<int> largestValues(TreeNode* root) 
    {
        vector<int> ret;
        if(root == nullptr) return ret;

        queue<TreeNode*> q;
        q.push(root);
        while(q.size())
        {
            int n = q.size();
            int _max = INT_MIN;
            for(int i = 0; i < n; i++)
            {
                auto t = q.front();
                q.pop();
                _max = max(_max, t->val);

                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ret.push_back(_max);
        }
        return ret;
    }
};

相关文章