本文共 2960 字，大约阅读时间需要 9 分钟。
近半年经常刷题，也参加了同学们自行组织的刷题会，到写这篇文章为止 leetcode 已经 AC 了 77 道题目了。时常的总结是必要的，而分享知识不仅能帮助自己树立知识脉络，更能帮助到大家，为学习算法的同学们提供一种参考的思路。
广度优先搜索（BFS）是在搜索中首先将所处位置的直接邻居访问一遍，再进入下一层重复之前操作的一种搜索。这种算法需要维护一个队列。队列有着先进先出（First In First Out）的性质。算法的开始一般都是把根节点加入到空队列中，然后开始一个结束条件是队列为空的循环。每一次循环中，算法会取得队列最前的一个元素并且访问它的所有邻居。在访问邻居的同时，程序会把邻居添加到队列中。至此广度优先搜索就写完了，程序会按照上述循环把能够访问到的节点都访问一遍。
这种算法可以应用在图，也可以应用在树上。下面我们来看几道跟树这种数据结构有关的题目。
这道题是典型的广度优先搜索，要求按层遍历树。解答如下：
"""# Definition for a Node.class Node(object): def __init__(self, val, children): self.val = val self.children = children"""class Solution(object): def levelOrder(self, root): """ :type root: Node :rtype: List[List[int]] """ if root is None: return [] queue = [(root, 0)] result = [] while queue: node, level = queue.pop(0) while len(result) <= level: result.append([]) result[level].append(node.val) for child in node.children: queue.append((child, level + 1)) return result
我们规定根节点是第 0 层，然后把节点和所在层级放在一个 tuple 里进队。循环的终止条件是队列为空，当队列有元素时，队头出队，我们对元素做一些处理，然后将它的子孙加入队列。在这个问题中，对于元素的操作比较简单，把它加入结果数组中即可。当然，加入之前要保证数组对应的位置有数组存在（结果是一个包含数组的数组），不然会抛出索引越界的异常。
是一道中等难度的题目，要求交叉遍历二叉树。交叉的意思是从根节点开始，根节点那层从左到右遍历，下一层从右到左，再下一层从左到右，依次循环直到最后一层，期间忽略 null.
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def zigzagLevelOrder(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ if root is None: return [] queue = [(root, 0, True)] result = [] while queue: node, level, left_to_right = queue.pop(0) while len(result) <= level: result.append([]) nodes_on_same_level = [node] while len(queue) > 0 and queue[0][1] == level: nodes_on_same_level.append(queue.pop(0)[0]) for n in nodes_on_same_level: if n.left: queue.append((n.left, level + 1, not left_to_right)) if n.right: queue.append((n.right, level + 1, not left_to_right)) if left_to_right: for n in nodes_on_same_level: result[level].append(n.val) else: for i in range(len(nodes_on_same_level) - 1, -1, -1): n = nodes_on_same_level[i] result[level].append(n.val) return result
题目依旧是要求按层遍历，所以广度优先搜索仍然是我选用的方法。于是读者可以发现本题解法和上一题有着很类似的结构，也有人称之为“套公式”。不同的第一处在于队列中的 tuple 现在有三个元素了，增加了末尾的一个布尔类型。该布尔变量值为 True 的时候说明当前层级需要从左往右遍历，反之从右往左。在循环中，程序一次性将一层的节点全部找出，按照布尔变量指定的顺序添加到结果数组中。剩下的工作就是将子节点进队，和上一题同样的是层级要加 1，不同的是要将布尔变量扭转后再存入队列。
这篇较短的博文首先概括了广度优先搜索的思想，然后通过两道难度有递进的题目进一步介绍了这种算法，希望大家在刷题道路上有更多收获；对我的文章、代码有指点的也欢迎评论，我会即时回复。
转载地址：http://hfpmb.baihongyu.com/