5.1　深度优先遍历

使用DFS进行解题的大概思路是定义起始节点和结束节点，从起点开始不断深入其他节点，在搜索的过程中判断是否满足特定条件，伪代码如下。

上面的visited是为了防止由于环的存在而造成死循环的，不管是BFS还是DFS，如果是在二维矩阵或图上进行搜索，通常都需要visited来记录节点访问状态。也可以使用原地标记，比如后面要讲的岛屿问题就使用了这个技巧。

如果在树的题目中使用DFS，由于树是不存在环的，因此有关树的题目大多数不需要visited，但是如果对树的结构做了修改，使之出现了环，那就仍然需要 visited。例如第138题复制带随机指针的链表，这道题需要记录已经复制的节点。因此一个树的DFS代码在更多情况下应该是下面这样的。

而几乎所有有关树的题目都是二叉树，因此下面这样的代码更常见。

由于二叉树的简洁性，建议读者从二叉树开始练习DFS和BFS，然后将这些思想和技巧推广到其他更复杂的数据结构，例如图。

对于二叉树的题目，除了递归出口的条件，还会写一些其他的逻辑，这些逻辑由于位置的不同，产生的效果也截然不同。根据DFS逻辑位置的不同，我们将其分为三种类型，一种是自顶向下（前序遍历）的，一种是自底向上（后序遍历）的，最后一种是中序遍历。

前序遍历就是在每个递归层级上首先访问节点来计算一些值，并在递归调用函数时将这些值传递到子节点，一般是通过参数传到子树中。

伪代码如下。

后序遍历是另一种常见的递归方法，首先对所有子节点递归地调用函数，然后根据返回值和根节点本身的值得到答案。

作者的经验总结如下。

●　大多数有关树的题目使用后序遍历会比较简单，并且大多需要依赖左/右子树的返回值。例如第1448题统计二叉树中好节点的数目。

●　也有一部分有关树的题目需要前序遍历，而前序遍历通常要结合参数扩展技巧。例如第1022题从根到叶的二进制数之和。

●　如果能使用参数和节点本身的值来决定应该传递给它的子节点的参数，那么就用前序遍历。

●　对于树中的任意一个节点，如果知道它子节点的答案，就能计算出当前节点的答案，那么就用后序遍历。

●　如果遇到二叉搜索树，则考虑使用中序遍历。

读者熟悉了二叉树的DFS技巧之后，再尝试将其推广到其他数据结构会轻松很多。