二叉树的BFS&打开转盘锁详解

• • BFS解决

近在做力扣学习学习数据结构与算法，评论区看到解决方案在此记录下。

BFS解决

以字符串"0000"为起始点，把它的每一位都分别加1和减1，总共会有8个结果，如下图所示，细心的同学可能发现了，这不就是一棵8叉树吗，二叉树是有2个子节点，那么8叉树肯定就是8个子节点了。

这是一棵以"0000"为根节点的8叉树，我们一层一层的遍历他的每个节点，如果找到就返回他所在的层数即可，如果当前层遍历完了还没找到就遍历下一层，直到找到为止，如果都遍历完了还没找到就返回-1。所以我们很容易想到BFS

注意这棵树并不是无线的延伸下去的，因为树中所有的节点都不能重复，否则会出现死循环。比如"0000"的子节点包含"0001"，但"0001"的子节点不能再包含"0000"了。
二叉树的BFS代码如下

public void levelOrder(TreeNode tree) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(tree);//相当于把数据加入到队列尾部
    while (!queue.isEmpty()) {
        //poll方法相当于移除队列头部的元素
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null)
            queue.add(node.left);
        if (node.right != null)
            queue.add(node.right);
    }
}

这里只是对二叉树的BFS打印，如果我们想要每一次的层数还可以改为下面这样

public void levelOrder(TreeNode tree) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(tree);
    int level = 0;//统计有多少层
    while (!queue.isEmpty()) {
        //每一层的节点数
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            //打印节点
            System.out.println(node.val);
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
        level++;
        //打印第几层
        System.out.println(level);
    }
}

二叉树的BFS打印我们搞懂了之后，那么不管是8叉树还是100叉树，打印其实都是一样的，我们来看下最终代码

import java.util.*;

/**
 * Created by leo on 2022/1/17.
 * BFS关键：设置哈希表存储deadends和记录已访问过的节点
 * 避免重复访问
 */
public class BFSTest {

	public int openLock(String[] deadends,String target){
		Set<String> set = new HashSet<>(Arrays.asList(deadends));
		//根节点 “0000”
		String startStr = "0000";
		if(set.contains(startStr)) return -1;
		//创建队列
		Queue<String> queue = new LinkedList<>();
		//记录访问过的节点
		Set<String> visited = new HashSet<>();
		queue.offer(startStr);
		visited.add(startStr);
		//树的层数
		int level = 0;
		while (!queue.isEmpty()){
			//每层的节点个数
			int size = queue.size();
			while(size-- >0){//八叉树   逐一遍历子节点
				String str = queue.poll();//队列删除并取值
				//如果找到直接返回
				if(str.equals(target)){
					return level;
				}
				//对于每个节点中的4个数字分别进行加1和减1，相当于创建8个子节点，这八个子节点
				//可以类比二叉树的左右子节点
                for(int i=0;i<4;i++){
	                char ch = str.charAt(i);
	                String strAdd = str.substring(0,i) + (ch == '9' ? 0 : ch - '0'+1)+str.substring(i+1);
	                String strSub = str.substring(0, i) + (ch == '0' ? 9 : ch - '0' - 1) + str.substring(i + 1);
	                //不能包含死亡数字也不能包含访问过的字符串
	                if(!visited.contains(strAdd) && !set.contains(strAdd)){
						queue.offer(strAdd);
						visited.add(strAdd);
	                }
	                if (!visited.contains(strSub) && !set.contains(strSub)) {
		                queue.offer(strSub);
		                visited.add(strSub);
	                }
                }
			}
			//当前层访问完了，到下一层，层数加1
			level++;
		}
		return -1;
	}
}

作者：数据结构和算法
链接：https://leetcode-cn.com/leetbook/read/queue-stack/kj48j/?discussion=5WQchG
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。