# 二叉树遍历算法
在上一篇中，我们简述了递归思维的重要性。这一篇我们开始正式的算法精华的学习。我决定将这重要的一篇贡献给二叉树算法。
可以说，二叉树算法是整个算法大厦的基石。二叉树算法可以拓展为多叉树算法，而多叉树的遍历正是广度优先搜索与深度优先搜索的基础。于此同时，树的遍历算法仅需加上环判断，即可升级为图的遍历算法。
可以说，学会了二叉树遍历算法，就掌握了所有数据结构的遍历法则，由此足以见得二叉树算法的地位。因此，理解与掌握本篇十分重要。
# 二叉树的深度优先的遍历方式
我们学过，二叉树的深度优先的遍历方式一共分为前中后序三种。但他们之间的区别是什么，以及是如何划分的呢？
实际上，划分的依据只有一句话，就是：每经过一个节点时，需要在什么时机进行运算与数据的输出。重点在于判断执行逻辑处理的时机。
所谓前序遍历，即指在某个节点，进入左右子节点之前，进行运算与输出数据。而中序指的是在遍历左子树完成后，在准备遍历右子树之前，进行运算与输出数据。同样的，后序遍历即在左右子树都遍历完成后，再进行计算与输出。
因此，DFS 的遍历框架就轻松整理出来了，如下所示：
function traverse(node: TreeNode | null) {
// 处理 base case，结束递归
if (!node) {
return;
}
// 此处进行前序遍历
traverse(node.left);
// 此处进行中序遍历
traverse(node.right);
// 此处进行后序遍历
}
当然，从这里也可以明显看出递归思维的简洁强大之处，能将不同的遍历方式以如此简单的形式呈现出来。
而使用递推法呢？其实借助循环与栈的形式也能实现上面的结构，但是写起来会比较繁琐，以前序与后序遍历为例，感受一下每次遍历需要控制变量变化时的写法复杂程度：
function traverse(node: TreeNode) {
const stack: TreeNode[] = [node];
while(stackLeft.length > 0) {
const curr = stackLeft.pop();
// 此处处理前序遍历逻辑
curr.left && stack.push(curr.left)
curr.right && stack.push(curr.right)
}
}
function traverse(node: TreeNode | null) {
const stack: TreeNode[] = [node];
// 记录上一个遍历逻辑处理过的节点
let prev: TreeNode;
while (node || stack.length > 0) {
// 先将所有左子树压栈
while (node !== null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
// 若该节点有右子树，将该节点压回栈中，并将指针移向右子树
if (node.right && node.right !== prev) {
stack.push(node);
node = node.right;
} else {
// 此处才可处理后序遍历逻辑
// 更新上一个出栈的节点，防止重复遍历
prev = node;
node = null;
}
}
}
我们可以发现，同样使用栈结构时，由于后序遍历时需要防止重复遍历，所考虑的边界情况更多，因此，写起来可读性要更差一些。
从上面的比较中我们可以看出，递归思维能让我们专注在梳理思路本身，而非纠结在变化细节上，是学习算法思路时必知必会的窍门。
# 如何选择合适的遍历方式
知道了二叉树的所有遍历方式，那么怎么判断在某种算法情形下，该使用那种遍历方式来解答呢？
由前面的介绍我们可以知道，合适的遍历方式即指在合适的时机处理数据。因此，我们需要知道每次遍历时所需要的数据要求。共会分为以下几种情形：
# 1. 无要求
如果题目的需求不在乎合适的时机，每个节点的数据处理都只关心自己节点的信息。
例如：求二叉树中，节点值为 1 的节点信息，那么无论前中后序遍历选用哪一种，自然都是可行的。
# 2. 要求前置节点信息
如果题目只需要知道进入当前节点时，当前节点与之前遍历过的节点的信息，那么三种遍历顺序也都是可行的。
因为在进入节点之前，上层的信息就已经可以获取到了。但通常来说，前序遍历是最为方便的选择。
例如：求二叉树中，路径上节点值之和的最大值。我们只需要定义一个全局变量，每经过一个节点时，将之前的和加上当前节点值与最大值比较即可。接着将新和递归传递给下一个子节点。
# 3. 要求子树的节点信息
如果题目要求，当前的运算必须依赖其子节点的结果，此时就只有后序遍历可以胜任了。
因为只有后序遍历的数据处理时机能拿到左右子树运算完成后的结果，此时才能对数据进行处理。
还是刚刚的问题，求路径上节点值和的最大值。我们可以换一个思路。不借助全局变量，如果每一个节点都能拿到左子树与右子树的路径值的和，那么去左右子树和的最大值加上当前节点值，即为当前节点下的最大值。那么只需要输出根节点的结果即可完成题目。
所以，哪怕对于同一个题目，看待题目的思路不同，解法也可以不同。
中序遍历的要求同理，如果有题目要求只需要知道左子树的信息来做运算，此时可以选择中序遍历。在此就不举例说明了。
题型参考：
[104] 二叉树的最大深度[543] 二叉树的直径
# 通过前中后序遍历反序列化出二叉树
在学习了二叉树是如何遍历之后，我们有时也会逆向思考，由遍历结果反推出二叉树的结构。
其实这种低维与高维的数据结构互转的方式在工程中也较为常用，称为序列化与反序列化，例如存储与还原一个DOM树形结构，利用享元模式压缩与解压复杂数据结构等等。
回到正题，说到构造二叉树的方式，其实只有一种：找到根节点，然后递归地构造左右子树。
要通过前中后序的遍历结果构造二叉树，首先我们得了解，每种遍历结果特点，与其构造树之间的关系。
前序遍历：对每一个子树都有，树的根节点一定是其前序遍历结果的第一个。 中序遍历：对每一个子树都有，根节点所在位置的左边即为其左子树的中序遍历结果；右边即为为其右子树的中序遍历结果。 后序遍历：对每一个子树都有，树的根节点一定是其前序遍历结果的最后一个。
通过前序遍历或者后序遍历结果，我们可以判断出根节点的值。通过找到中序遍历的根节点的位置，我们可以判断出其左子树与右子树的节点个数。再通过前序遍历或后序遍历，得到前（后）序遍历的左右子树的起止位置。
从以上的特性中我们可以推论出：知道前序与中序结果、后序与中序结果，此种情况下构造出的二叉树是唯一的。
而知道前序与后序结果构造二叉树的方式，其结果不一定是唯一的。因为当节点仅有一棵子树时，无法判断其是左子树还是右子树。
在通过前序遍历得出根节点的值之后，左子树的根节点为前序遍历的第二个节点，在后序遍历中找到该左子树根节点的位置，从而可以得出后序遍历的左子树的节点个数。之后的方式就与之前的相同了，得到两种遍历的左右子树的起止位置。
题型参考：
[105] 从前序与中序遍历序列构造二叉树[106] 从中序与后序遍历序列构造二叉树[889] 根据前序和后序遍历构造二叉树
# 二叉树的层序遍历方式
除了 DFS 的深度优先遍历外，二叉树还可以以广度优先搜索的方式来遍历所有节点，也就是所谓的层序遍历法。即每一次遍历处理一层的节点。
其核心数据结构是队列。我们需要维护一个队列，每次从队尾取出需要遍历的节点，并在逻辑结束后将遍历节点的子节点入队，作为下一层遍历时的节点使用。
所谓的 BFS 框架，其遍历顺序就是基于层序遍历的模式。因此树的层序遍历法也是 BFS 算法的基础。
这样的遍历方式多用于求树的最小高度，树的最短路径等等。在这些情况下，绝大多数时候可以在不用遍历完整棵树前得出答案，效率较 DFS 遍历方式高。
const queue = [root];
let depth = 1;
while(queue.length > 0) {
let len = queue.length;
while(len--) {
const node = queue.shift();
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
depth += 1;
}
题型参考：
[111] 二叉树的最小深度