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++;
    }
}

二叉树的最小深度

题目：
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 递归版本
    int min2(TreeNode root) {
        if(root == null) return 0;
        int left = min2(root.left);
        int right = min2(root.right);
        if(left != 0 && right != 0) {
            return 1 + Math.min(left, right);
        } else {
            return 1 + left + right;
        }
    }

    public int minDepth(TreeNode root) {
        return min2(root);
    }

    // 非递归版本
    public int minDepth2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        LinkedList<TreeNode> nextList = new LinkedList<>();
        int depth = 1;
        list.add(root);
        while(true) {
            if(list.isEmpty()) {
                if(nextList.isEmpty()) break;
                depth++;
                list = nextList;
                nextList = new LinkedList();
            }
            TreeNode node = list.removeFirst();
            if(node == null) {
                continue;
            }
            if(node.left == null && node.right == null) {
                break;
            }
            nextList.add(node.left);
            nextList.add(node.right);
        }

        return depth;
    }
}

转盘锁

题目：
https://leetcode-cn.com/problems/open-the-lock/

class Solution {

    List<Character> nums;
    
    public int openLock(String[] deadLocks, String target) {
        nums = Arrays.asList('0', '1', '2', '3', '4', '5', '6', '7', '8', '9');
        List<String> deadLockList = Arrays.asList(deadLocks);

        Set<String> list = new HashSet<>();
        Set<String> list2 = new HashSet<>();
        list.add("0000");
        list2.add(target);
        Set<String> visited = new HashSet<>(list);

        if (deadLockList.contains(target) || deadLockList.contains("0000")) {
            return -1;
        }

        visited.addAll(deadLockList);
        int step = 0;
        while (!list.isEmpty()) {
            Set<String> tmp = new HashSet<>(list);
            for (String lock : tmp) {
                list.remove(lock);
                if (list2.contains(lock)) {
                    return step;
                }
                visited.add(lock);

                LinkedList<String> nextLocks = getNextLocks(lock);
                for (String nextLock : nextLocks) {
                    if (visited.contains(nextLock)) {
                        continue;
                    }
                    list.add(nextLock);
                }
            }
            step++;
            Set<String> swap = list;
            list = list2;
            list2 = swap;
        }

        return -1;
    }

    LinkedList<String> getNextLocks(String lock) {
        LinkedList<String> nextLocks = new LinkedList<>();
        for (int i = 0; i < lock.length(); i++) {
            StringBuilder newLock = new StringBuilder(lock);
            int index = nums.indexOf(newLock.charAt(i));
            char nextChar = nums.get((index + 10 + 1) % 10);
            newLock.replace(i, i + 1, String.valueOf(nextChar));
            nextLocks.add(newLock.toString());

            nextChar = nums.get((index + 10 - 1) % 10);
            newLock.replace(i, i + 1, String.valueOf(nextChar));
            nextLocks.add(newLock.toString());
        }
        return nextLocks;
    }

}