算法面试——广度优先搜索：层序遍历、最小步数

BFS 适合求最短路径/最小步数问题。核心是用队列逐层扩散。

一、二叉树的层序遍历

publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>result=newArrayList<>();if(root==null)returnresult;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();List<Integer>level=newArrayList<>();for(inti=0;i<size;i++){TreeNodenode=queue.poll();level.add(node.val);if(node.left!=null)queue.offer(node.left);if(node.right!=null)queue.offer(node.right);}result.add(level);}returnresult;}

二、打开转盘锁

publicintopenLock(String[]deadends,Stringtarget){Set<String>dead=newHashSet<>(Arrays.asList(deadends));Set<String>visited=newHashSet<>();Queue<String>queue=newLinkedList<>();if(dead.contains("0000"))return-1;queue.offer("0000");visited.add("0000");intsteps=0;while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;i++){Stringcur=queue.poll();if(cur.equals(target))returnsteps;for(Stringnext:getNext(cur)){if(!dead.contains(next)&&!visited.contains(next)){visited.add(next);queue.offer(next);}}}steps++;}return-1;}

三、单词接龙

publicintladderLength(StringbeginWord,StringendWord,List<String>wordList){Set<String>wordSet=newHashSet<>(wordList);if(!wordSet.contains(endWord))return0;Queue<String>queue=newLinkedList<>();queue.offer(beginWord);intsteps=1;while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;i++){Stringcur=queue.poll();char[]chars=cur.toCharArray();for(intj=0;j<chars.length;j++){charoriginal=chars[j];for(charc='a';c<='z';c++){chars[j]=c;Stringnext=newString(chars);if(next.equals(endWord))returnsteps+1;if(wordSet.contains(next)){queue.offer(next);wordSet.remove(next);}}chars[j]=original;}}steps++;}return0;}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！