上一章我们从0到1的实现了一颗二叉搜索树，以及理解了二叉搜索树的特性与基本操作，这一章介绍关于二叉树的更多操作，也就是树的遍历。主要包括前序遍历、中序遍历、后序遍历、层序遍历，前面三种也叫深度优先遍历(DFS)，最后的层序遍历也叫广度优先遍历(BFS)，理解这四种遍历方式的不同，再遇到树相关的算法问题时，也就能更加游刃有余。这里不单指二叉搜索树，遍历思想同样适用于多叉树。
深度优先顾名思义，首先从树的深度开始，也就是优先访问完其中一棵子树，然后再去访问另一颗子树。树的深度优先里又分为前/中/后序遍历，它们的区别仅仅是当访问到具体的节点时，它们先后顺序的不同。深度优先一般都是采用递归的方式实现，因为好理解，当然也可以使用遍历实现，不过那样会增加代码复杂性以及代码的语义化。(LeetCode上后序遍历的非递归实现可是困难难度)
也就是靠前访问到树的节点，首先贴出代码，给上一章实现的二叉搜索树增加前序遍历的方法：
无论使用哪种遍历方式都是为了访问到树的每个节点，注意上面代码里函数fn的位置，它位于两个递归函数的前面，所以叫它前序遍历；而中序遍历fn就是在两个递归函数的中间；后序遍历fn就是在两个递归函数的后面，它们叫法的由来，也是仅此而已。虽然是这么一点点的区别，然而结果相差挺大且应用方式的区别也很大，首先来看下前序遍历：
当使用前序遍历时，它的访问顺序是15、10、7、12、26、22、37。它的访问特点是首先访问这棵树的根节点，然后访问它的左子树，最后是访问右子树，这也是看起来比较符合直觉的一种遍历方式。如果还是不太好理解的话，可以将一整颗树分解来理解：
因为是前序遍历，首先遇到子树A，此时它的根节点是15，被访问到。然后去它的左子树B，节点10又是子树B的根节点，所以被访问到。再去节点7与两个null构成的子树，节点7被访问到，因为7的左右孩子都是null，所以返回到父节点10，最后去访问右节点12，整棵树的左子树就访问完了。然后再右子树实行同样的规则进行访问。以此类推也就形成了刚才看到的访问顺序结果，知道它的访问顺序有什么用？那就以一道算法题来看其应用。
必须要高度平衡，所以不能出现一边高一点低的情况。该题有个条件是在一个有序的数组集合里，所以再重构这颗树时，根节点就可以选择数组的中间位置，因为剩下左侧部分全部是小于根节点的，而右侧部分全部是大于根节点的，正好符合二叉搜索树的定义。以此类推剩下部分的根节点依然中间位置，从而进行左右的分割，直到最后不能进行分割即可。
为什么不采用(l + r) / 2，而采用l + (r - l) / 2的书写方式，是为了防止出现整型溢出的情况。因为数组里每一项的值首先需要实例化为树的节点TreeNode，才能创建它的左孩子和右孩子，所以采用前序遍历的方式。整棵树的构建顺序也是先根节点，然后左子树，最后右子树的顺序完成。
仅仅只是改变了访问节点的顺序，首先访问左子树，然后访问当前根节点，最后访问右子树。还是贴出代码：
就是简单的更改了访问节点的位置，顺序也很有意思：
结果是7、10、12、15、22、26、37，正好是一个升序排列方式，这也是二叉搜索树使用中序遍历的一个特点，如果理解了之前前序遍历递归函数的运行过程，中序遍历理解起来就不难了。因为首先是访问完左子树，只要左孩子不是null，递归函数就会一直往左侧访问，而二叉搜索树最小的节点正好最左侧的叶子节点，到了底部之后则开始采用左中右的递归顺序往回走，正好是一个升序排列。它有啥用？还是使用一个算法题来看其应用。
看题目不是太好理解，就以我们示例的二叉搜索树为例：
按照该题的算法，解为2，因为任意两个之间的绝对值，这是最小的。一下没有想到解题的思路？没事，假如我们把这颗二叉搜索树看成是一个升序数组[7, 10, 12, 15, 22, 26, 37]，求解该数组任意两个值之间差的最小绝对值。不难发现其实"任意"是个幌子，你只能去比较两个相连数字它们的绝对值。再去看二叉搜索树，也就明白了，使用中序遍历，比较两个前后访问的节点即可得到"任意"两个节点的最小绝对值差。
使用一个prev变量缓存上一次访问的节点，每一次让当前访问到的节点值减去之前节点的值，因为是中序遍历，所以当前节点的值一定是大于之前节点的，将整颗树遍历完，返回两两相减最小的值即可。
也是仅仅改变访问节点的位置即可，先访问左子树，再访问右子树，最后访问自身根节点，贴代码：
先访问完左子树，然后是右子树，最后是自身节点，访问顺序如下：
简单来说就是每个节点的坡度等于它左右子树和的绝对差，所以叶子节点的坡度就是0，因为左右孩子都是空节点，返回的就是0-0的值。进行子问题拆解的话，可以理解为整颗树的坡度就是它的左右子树坡度之和，所以需要先求出左右孩子的坡度才能计算出当前节点的坡度，后序遍历非常适合。
解题代码如下：
以上三道算法题，分别展示了树的前/中/后序遍历的实际应用，这些还远远不够。有的算法题常规的遍历方式并不能太好解决问题，这个时候就需要在深刻理解了树的(DFS)遍历特性后，进行额外灵活的处理来解决。
题目不好懂，不过从转换的示例可以看出，从右子树最右叶子节点开始，进行两两的节点值累加，最终从右到左的累加完整棵树。如果把这颗二叉搜索树看成是一个数组[7,10,12,15,22,26,37]，那么它的操作就是数组从后往前的进行两两相加并覆盖前一个值。对于树的话，我们就需要进行反常规的中序遍历，首先遍历右子树，然后遍历根节点，最后遍历左子树，也就是进行一次降序遍历。
题目的要求是从根节点到叶子节点，所以要记录每一步的当前节点，而前序遍历的顺序正好可以记录从根到叶子节点的整条路径。而这道题有意思的地方在于前序遍历返回时，需要把最后一步的叶子节点从路径里移除掉，重新添加另外的节点路径值，所以可以在后序遍历的顺序里，像贪吃蛇一样一口口的去吃掉已经访问过的路径。有人把这种解法取了个挺厉害的名叫回溯。代码如下：
深度优先是先遍历完一棵子树，再遍历完另一颗子树，而广度优先的意思是按照树的层级一层层的访问每个节点，图示如下：
当然你也可以从右往左的打印，打印顺序就是15、26、10、37、22、12、7，广度优先的实现我们需要借助另外一种数据结构《队列》，因为普通的队列理解起来并不复杂，所以之前的章节也没有单独介绍。正好到了树的层序遍历，在这里可以将队列的定义及其应用一并介绍。
之前的章节我们介绍了栈，这是一种一端堵死，后进先出的数据结构。而队列则有不同，没有哪头堵死，从队尾进入，队首出队的一种顺序数据结构。
这也是一种受控的数据结构，提供的接口只能访问到队尾和队首，中间的元素外部无法访问到。
使用队列，将每个节点入队，同时在出队一个节点后，将它的两个孩子节点入队。首先入队根节点，然后出队根节点的同时，入队它的两个孩子节点，此时队列不为空，继续采用同样的方式入及出队接下来的节点。
代码实现如下：
这个完全就是为了层序遍历而量身定制的，不过和常规的遍历有所不同，需要求出每一层的平均值，也就是说在遍历完一层的时候，我们需要知道这一层已经遍历完了，这样才可以求出平均值。可以在while循环内再加一个针对每一层的循环，代码如下：