树的遍历是一个基础问题，也有很多的实际应用，可以用来找到匹配的字符串，文本分词和文件路径等问题。
树的遍历有两个基本的方法：深度优先遍历 和 广度优先遍历。深度优先遍历又可以根据处理节点的顺序不同，可以分为：中序遍历，前序遍历和后序遍历。这些知识点也是深度优先遍历经常考察的。
广度优先遍历的考察在于层次遍历。比如需要我们按照层次输出一棵树的所有节点的组合(LeetCode 107)，比如求一棵树的最左节点(LeetCode 513)，比如求一棵树的每层的最大值的集合(LeetCode 515)。这些问题本质上都是考察的广度优先遍历。
如下代码是经典的广度优先遍历实现方式，使用了队列的FIFO的方式，将所有暂未访问的节点存入一个队列中，依次遍历。
queue = [node] # 新建一个队列，并将根节点放入队列
while queue.length != 0
item = queue.shift #弹出队列的头部元素
do_something(item) # 操作该节点：比如存入一个数组或者打印
queue.push(item.left) if item.left # 将左子节点存入队列
queue.push(item.right) if item.right # 将右子节点存入队列
但是只掌握了上面的遍历方法是不够的，层次遍历的难点在于同层次的比较。也就是说，我们需要对不同层次的节点做隔离。下面我们总结了三种不同层次的节点隔离的技巧。
思路
获取当前的队列的长度 length, 一次只遍历只遍历 length 个节点，后续加入的元素在下一次循环遍历。
伪代码如下
queue = [node] # 新建一个队列，并将根节点放入队列
while queue.length != 0
length = queue.length # 获取当前队列的长度
while length > 0 # 只弹出 length 个节点
item = queue.shift #弹出队列的头部元素
do_something(item) # 操作该节点：比如存入一个数组或者打印
queue.push(item.left) if item.left # 将左子节点存入队列
queue.push(item.right) if item.right # 将右子节点存入队列
length--
思路
在不同层的节点中间加入一个分隔符，遍历到分割几点的时候，停止当前遍历。
伪代码如下
queue = [node] # 新建一个队列，并将根节点放入队列
while queue.length != 0
queue.push "$" # 将分割符放入队列
while(true) # 做一个无限循环
item = queue.shift #弹出队列的头部元素
break if item == '$' # 如果当前的节点等于分隔符，说明该层已经遍历到了最右边
do_something(item) # 操作该节点：比如存入一个数组或者打印
queue.push(item.left) if item.left # 将左子节点存入队列
queue.push(item.right) if item.right # 将右子节点存入队列
思路
用一个 level 字段来保存深度，在深度优先遍历的时候，判断一下当前节点的深度即可。
伪代码如下
ans = [] # 用一个数组来保存值
level = 0 # 跟节点的 level 是 0
visit(node, ans, level)
def visit(node, ans, level):
return if node is null #如果节点为空，则返回
# 逻辑处理部分
if ans.length > level # 说明之前访问过该层的节点
ans[level].push node.val
else # 说明当前level没有访问过
ans[level] = [node.val]
visit(node.left, level + 1, ans)
visit(node.right, level + 1, ans)
逻辑处理部分的代码还有一个需要注意的地方，比如 LeetCode 107 需要求 reverse 后的结果，所以在处理这部分逻辑的代码时，需要找到当前 level 对应的数组的 position。
使用 BFS + Level 字段的优势在于代码更简单，逻辑跟清晰。难点在于逻辑部分的处理需要小心一些。
树的难点在与树的构造，需要将一般性问题抽象成一颗树，需要定义好节点和路径。当我们构造好一颗树后，一般只需要遍历这棵树就能得到结果。所以，树的遍历是一个基础问题。其中分层遍历的技巧比 DFS/BFS 更难点，需要 coder 有更强的逻辑思维能力。
预告：下一篇打算写一篇矩阵遍历的技巧。
