BFS 适合求最短路径/最小步数问题。核心是用队列逐层扩散。一、二叉树的层序遍历publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerresultnewArrayList();if(rootnull)returnresult;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();ListIntegerlevelnewArrayList();for(inti0;isize;i){TreeNodenodequeue.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){SetStringdeadnewHashSet(Arrays.asList(deadends));SetStringvisitednewHashSet();QueueStringqueuenewLinkedList();if(dead.contains(0000))return-1;queue.offer(0000);visited.add(0000);intsteps0;while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){Stringcurqueue.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,ListStringwordList){SetStringwordSetnewHashSet(wordList);if(!wordSet.contains(endWord))return0;QueueStringqueuenewLinkedList();queue.offer(beginWord);intsteps1;while(!queue.isEmpty()){intsizequeue.size();for(inti0;isize;i){Stringcurqueue.poll();char[]charscur.toCharArray();for(intj0;jchars.length;j){charoriginalchars[j];for(charca;cz;c){chars[j]c;StringnextnewString(chars);if(next.equals(endWord))returnsteps1;if(wordSet.contains(next)){queue.offer(next);wordSet.remove(next);}}chars[j]original;}}steps;}return0;} 觉得有用的话点赞 关注【张老师技术栈】吧
