二叉树的前序、中序和后序遍历

type

status

date

slug

summary

遍历一棵树是指访问树的每个节点并对它们进行某种操作的过程。但是我们应该怎么去做呢？访问树的所有节点有三种方式：前序、中序和后序。需要注意的是：这里的前、中、后指的是针对根节点的访问顺序而言的。

前序遍历是以优先于后代节点的顺序访问每个节点的。

前序遍历会先访问节点本身，然后再访问它的左侧子节点，最后是右侧子节点。下面描绘了 preOrderTraversal 方法的访问路径：

控制台的输出结果：11, 7, 5, 3, 6, 9, 8, 10, 15, 13, 12, 14, 20, 18, 25

中序遍历是一种以上行顺序访问所有节点的遍历方式。

中序遍历会递归调用相同的函数来访问左侧子节点，接着对节点本身进行操作，然后再访问右侧子节点。下面描绘了 inOrderTraversal 方法的访问路径：

控制台的输出结果：3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 20, 25

后序遍历则是先访问节点的后代节点，再访问节点本身。

后序遍历会先访问左侧子节点，然后是右侧子节点，最后是节点本身，下面描绘了 postOrderTraversal 方法的访问路径：

控制台的输出结果：3, 6, 5, 8, 10, 9, 7, 12, 14, 13, 18, 25, 20, 15, 11

从三种遍历方式的代码可以看出，它们的实现方式是很相似的，唯一不同的就是操作节点的位置。

讲完了前序、中序和后续的遍历方式，我们来看两道经典的二叉树算法题，在面试过程中也经常会被问到。

我们会以下面这棵树为例，来分析接下来的两个算法。（两道题均为 Leetcode 原题，对应第 105 题和第 106 题）

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路：

通过观察可以发现，前中后序的遍历结果分别有一下特点：

所以对于这道题，我们首先根据前序遍历的结果的第一个值可以确定整棵树的根节点，之后找到根节点在中序遍历结果的位置，将中序遍历分成两段，左边部分就是左子树的中序遍历结果，右边部分就是右子树的中序遍历结果，那么我们怎么得到这两段对应的前序遍历的结果呢？可以根据长度，从前序遍历的结果中得到。

根据这个思路，我们可以递归地调用下去，代码实现如下：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

这道题和上面那道题的区别就在于一个是用前序遍历的第一个元素来确定根元素，另一个是用后序遍历的最后一个元素来确定跟元素。

所以根据上一题的代码，我们只需要在划分左右子树的时候，改一下标准：

代码均在 Leetcode 上测试通过。