【刷题19】队列+bfs专题

一、N叉树的层序遍历

题目：

思路：队列+bfs（具体看注释）

代码：

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ret;
        if(root == nullptr) return ret;
        queue<Node*> q; // 队列
        q.push(root);
        while(!q.empty())
        {
            // 统计一层的节点数
            int k = q.size();

            // 在同一层的所有节点值存在一个vector里
            // 同时统计当前节点的孩子节点个数，
            // 并把当前节点的孩子节点都放入队列中
            // 删除当前节点(队头)，root->下个队头节点
            vector<int> v;
            while(k--)
            {
                v.push_back(root->val);
                //
                int size = root->children.size();
                for(int i=0; i<size;i++)
                {
                    q.push(root->children[i]);
                }
                //
                q.pop();
                root = q.front();
            }
            ret.push_back(v);
        }
        return ret;
    }
};

二、二叉树的锯齿形层序遍历

题目：

思路：队列+bfs – 与上题大体相同（当前节点的孩子节点入队列不同）

• 因为是“锯齿形”层序，所以可以用一个变量来控制一个vector是否要逆序

代码：

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(root == nullptr) return ret;
        queue<TreeNode*> q; // 队列
        q.push(root);
        int t = 1;
        // 1: 不逆序
        // -1: 逆序
        while(!q.empty())
        {
            int k = q.size();

            vector<int> v;
            while(k--)
            {
                v.push_back(root->val);
                //
                if(root->left) q.push(root->left);
                if(root->right) q.push(root->right);
                //
                q.pop();
                root = q.front();
            }
            // t
            if(t < 0) reverse(v.begin(), v.end()); 
            t *= -1; 
            ret.push_back(v);
        }
        return ret;
    }
};

三、二叉树的最大宽度

题目：

思路：用数组模拟队列

• 数组中的元素是KV，分别表示节点指针和标记的数据
  
• 新节点入队列的操作与前面不同，需要用一个临时的数组，把当前层的所有节点的孩子节点放入临时数组，然后再覆盖原来的“队列”
• 计算最大宽度，当前层的第一个节点和最后节点的value值相减再+1
• 注意数据类型，用无符号的int

代码：

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(y2-y1+1, ret);

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

四、在每个树行中找最大值

题目：

思路：

• root为空，直接返回空的ret
• 剩下的与层序遍历思路一样，多了比较当前层的最大值，然后最大值放入ret中
• 注意节点值的数据范围

代码：

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ret;
        queue<TreeNode*> q;
        if(root == nullptr) return ret;//
        q.push(root);//
        while(!q.empty())
        {
            int max = INT_MIN;//
            int k = q.size();
            while(k--)
            {
                if(root->val > max) max = root->val; 
                if(root->left) q.push(root->left);
                if(root->right) q.push(root->right);
                q.pop();
                root = q.front();
            }
            ret.push_back(max);
        }
        return ret;
    }
};