例題： 797.?所有可能的路徑

模板題

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名注冊、網(wǎng)頁空間、營銷軟件、網(wǎng)站建設(shè)、察哈爾右翼中旗網(wǎng)站維護、網(wǎng)站推廣。

class Solution
{
public:
    vector>allPathsSourceTarget(vector>& graph)
    {
        vector>ans;
        queue>q;
        vectorv{ 0 };

        q.push(v);

        while (q.empty() == false)
        {
            v = q.front();
            q.pop();
            int node = v.back();

            if (node == graph.size() - 1)
            {
                ans.push_back(v);
            }
            else
            {
                for (auto i : graph[node])
                {
                    vectortemp = v;
                    temp.push_back(i);
                    q.push(temp);
                }
            }
        }

        return ans;
    }
};

102.?二叉樹的層序遍歷

廣度優(yōu)先搜索在二叉樹中的直接應(yīng)用

class Solution
{
public:
    vector>levelOrder(TreeNode* root)
    {
        vector>ans;       //返回的答案二維數(shù)組
        if (root == nullptr)           //防止樹為空
        {
            return ans;
        }

        queueq;
        vectorv{ root->val };

        ans.push_back(v);             //手動存入根節(jié)點的值，不然會出錯
        q.push(root);                 //將根節(jié)點進入隊列，作為BFS的“源”

        while (q.empty() == false)    //外層的while循環(huán)是針對二叉樹中的每一層，一次循環(huán)便是一層
        {
            vectortemp;
            int size = q.size();

            for (int i = 0; i< size; i++)  //內(nèi)層的for循環(huán)是針對一層中所有節(jié)點的遍歷
            {
                TreeNode* r = q.front();
                q.pop();

                if (r->left != nullptr)          //先左節(jié)點，后右節(jié)點，順序不能錯
                {
                    q.push(r->left);
                    temp.push_back(r->left->val);
                }
                if (r->right != nullptr)
                {
                    q.push(r->right);
                    temp.push_back(r->right->val);
                }
            }

            if (temp.empty() == false)     //防止答案中出現(xiàn)空的temp
            {
                ans.push_back(temp);
            }
        }

        return ans;
    }
};

練習： 733.?圖像渲染

class Solution
{
public:
    vector>floodFill(vector>& image, int sr, int sc, int color)
    {
        int oldColor = image[sr][sc];
        queue>q;
        pairp(sr, sc);

        if (oldColor == color)
        {
            return image;
        }

        q.push(p);
        image[sr][sc] = color;

        while (q.empty() == false)
        {
            pairtemp;
            p = q.front();
            q.pop();

            if (p.first >0
                && image[p.first - 1][p.second] == oldColor)
            {
                temp.first = p.first - 1;
                temp.second = p.second;
                image[temp.first][temp.second] = color;
                q.push(temp);
            }
            if (p.first< image.size() - 1
                && image[p.first + 1][p.second] == oldColor)
            {
                temp.first = p.first + 1;
                temp.second = p.second;
                image[temp.first][temp.second] = color;
                q.push(temp);
            }
            if (p.second >0
                && image[p.first][p.second - 1] == oldColor)
            {
                temp.first = p.first;
                temp.second = p.second - 1;
                image[temp.first][temp.second] = color;
                q.push(temp);
            }
            if (p.second< image[p.first].size() - 1
                && image[p.first][p.second + 1] == oldColor)
            {
                temp.first = p.first;
                temp.second = p.second + 1;
                image[temp.first][temp.second] = color;
                q.push(temp);
            }
        }

        return image;
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文標題：廣度優(yōu)先搜索（BFS）-創(chuàng)新互聯(lián)
文章位置：http://weahome.cn/article/ddihej.html