LeetCode广度优先遍历算法题目总结（一）

参考了《labuladong 的算法小抄》之BFS 算法解题套路框架。

广度优先算法核心思想就是图的广度优先遍历，关键操作在保存与当前访问节点的相连节点和节点的访问状态，其套路和框架伪代码如下：

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

111. 二叉树的最小深度

暴力递归

AC代码：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (NULL == root) {
            return 0;
        }
        int a = minDepth(root->left);
        int b = minDepth(root->right);
        if (0 == a) return b + 1;
        if (0 == b) return a + 1;
        return a > b ? b + 1 : a + 1;
    }
};

耗时320 ms，这一方法的思路是后序遍历左右子树，这一方法遍历了整棵树，同时包含递归操作，耗时很长，因此，进一步使用如下解法。

广度优先遍历（树的层序遍历）

AC代码：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (NULL == root) {
            return 0;
        }
        queue<TreeNode *> que;
        int depth = 1;
        que.push(root);
        // 层序遍历，每循环一次就遍历一层节点
        while (0 != que.size()) {
            int sz = que.size();
            for (int i = 0 ; i < sz; i++) {
                TreeNode *node = que.front();
                que.pop();
                // 层序遍历时，碰到的第一个叶子节点，就是这个二叉树深度最小的位置
                if (NULL == node->left && NULL == node->right) {
                    return depth;
                }
                if (NULL != node->left) que.push(node->left);
                if (NULL != node->right) que.push(node->right);
            }
            // 继续遍历下一层
            depth += 1;
        }
        return depth - 1;
    }
};

耗时264 ms，此方法使用了二叉树的层序遍历，层序遍历时，碰到的第一个叶子节点，即为这个二叉树深度最小的位置。

752. 打开转盘锁

广度优先遍历（树的层序遍历）

AC代码：

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        if (0 == target.compare("0000")) {
            return 0;
        }
        // 保存访问过的节点，避免走回头路
        unordered_set<string> visited;
        // 将死亡数字放入visited，因为死亡数字也不可访问
        visited.insert(deadends.begin(), deadends.end());
        // 边界条件，即"0000"为死亡数字
        if(visited.end() != visited.find("0000")) {
            return -1;
        }
        queue<string> que;
        // 保存起始状态
        que.push(string("0000"));
        visited.insert("0000");
        int step = 0;
        while (0 != que.size()) {
            int sz = que.size();
            // 判断上一次保存的状态中是否有目标状态
            for (int i = 0 ; i < sz ; i++) {
                string str = que.front();
                que.pop();
                if (0 == str.compare(target)) {
                    return step;
                }
                // 遍历下一步可能发生的状态，并将这些状态都保存到队列中
                for (int j = 0 ; j < 4 ; j++) {
                    string temp = str;
                    //分别在4位数字上加1减一
                    Update(j,1,temp);
                    if (visited.end() == visited.find(temp)) {
                        visited.insert(temp);
                        que.push(temp);
                    }
                    temp = str;
                    Update(j,-1,temp);
                    if (visited.end() == visited.find(temp)) {
                        visited.insert(temp);
                        que.push(temp);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    void Update(int pos, int temp, string &str) {
        if (temp > 0 && str[pos] == ‘9‘) {
            str[pos] = ‘0‘;
            return;
        }
        if (temp < 0 && str[pos] == ‘0‘) {
            str[pos] = ‘9‘;
            return;
        }
        str[pos] = str[pos] + temp;
        return;
    }
};

耗时196 ms，此方法将寻找目标状态转化为对树的层序遍历，即对八叉树（对节点上对应的四位数字分别加一减一）进行层序遍历，并根据deadends来为这棵树进行剪枝，同时，根据visited来防止重复访问父节点。

LeetCode广度优先遍历算法题目总结（一）

原文：https://www.cnblogs.com/hjxrupert/p/14636770.html