BFS需要一个marked来记录是否访问过该点，需要记录到达该点所需步数，需要一个队列来存储点。 marked可以用dict，但是可以不用一上来先遍历一遍所有点并把它们添加到marked里面然后设置其值为1，而可以在BFS循环时每遇到一个再给里面加一个。marked也可以用set。 记录步数可以不用额外的变量，而可以在队列中直接存储tuple(点，步数）。 队列可以使用
from queue import Queue q = Queue()也可以使用
import collections queue = collections.deque([(beginWord, 1)]) # 不能不加[] queue.append((word, level + 1)) current_word, level = queue.popleft()还可以不使用队列，而使用列表，每次循环都把同一深度的点遍历完，同时记录下一深度的点，等到下一次循环的时候去遍历：
class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: aux = [(0,0)] n = len(grid) if n == 1 and grid[0][0] == 0: return 1 if grid[0][0] == 1: return -1 cnt = 1 grid[0][0] = 1 directions = [(-1,1), (0,1), (1,-1), (1,0), (1,1)] while aux: t = [] for i in aux: for d in directions: x = i[0] + d[0] y = i[1] + d[1] if x < 0 or y < 0 or x == n or y == n or grid[x][y]: continue if x == n - 1 and y == n - 1: return cnt + 1 grid[x][y] = 1 t.append((x,y)) cnt += 1 aux = t return -1也可以用None给列表分层，每次遇到None就代表一层遍历完了，但在规模比较大时，list的pop(0)很耗时，因为是O(n)：
def maxDepth(self, root: TreeNode) -> int: if not root: return 0 q, depth = [root, None], 1 while q: node = q.pop(0) if node: if node.left: q.append(node.left) if node.right: q.append(node.right) elif q: q.append(None) depth += 1 return depthBi-directional BFS 需要两个marked，两个队列 完成条件是在一个方向搜索到的点是另一个方向的marked marked可以不是0,1的dict，而直接记录步数。 该方法可以减缓每层各个点的branch数量一样时的指数爆炸。
from collections import defaultdict class Solution(object): def __init__(self): self.length = 0 # Dictionary to hold combination of words that can be formed, # from any given word. By changing one letter at a time. self.all_combo_dict = defaultdict(list) def visitWordNode(self, queue, visited, others_visited): current_word, level = queue.popleft() for i in range(self.length): # Intermediate words for current word intermediate_word = current_word[:i] + "*" + current_word[i+1:] # Next states are all the words which share the same intermediate state. for word in self.all_combo_dict[intermediate_word]: # If the intermediate state/word has already been visited from the # other parallel traversal this means we have found the answer. if word in others_visited: return level + others_visited[word] if word not in visited: # Save the level as the value of the dictionary, to save number of hops. visited[word] = level + 1 queue.append((word, level + 1)) return None def ladderLength(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: List[str] :rtype: int """ if endWord not in wordList or not endWord or not beginWord or not wordList: return 0 # Since all words are of same length. self.length = len(beginWord) for word in wordList: for i in range(self.length): # Key is the generic word # Value is a list of words which have the same intermediate generic word. self.all_combo_dict[word[:i] + "*" + word[i+1:]].append(word) # Queues for birdirectional BFS queue_begin = collections.deque([(beginWord, 1)]) # BFS starting from beginWord queue_end = collections.deque([(endWord, 1)]) # BFS starting from endWord # Visited to make sure we don't repeat processing same word visited_begin = {beginWord: 1} visited_end = {endWord: 1} ans = None # We do a birdirectional search starting one pointer from begin # word and one pointer from end word. Hopping one by one. while queue_begin and queue_end: # One hop from begin word ans = self.visitWordNode(queue_begin, visited_begin, visited_end) if ans: return ans # One hop from end word ans = self.visitWordNode(queue_end, visited_end, visited_begin) if ans: return ans return 0