一、前言
上一篇中介绍了如何采用 DFS 和 BFS 的搜索思想去实现二叉树的前序遍历、中序遍历、后序遍历以及分层遍历。
这一节主要介绍 Medium 难度中比较常见的一种题型：根据各种遍历构造二叉树。
二、1008. 先序遍历构造二叉树
返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点
本道题目要求构造一棵 BST，使得它的前序遍历序列与给定的 preorder 匹配。
首先，对二叉树进行前序遍历，可以得到如下序列：
代码语言：rust复制 根节点 --> 左子树 --> 右子树显然，根据前序序列，可以确定第一个元素就是根节点，那么接下来的问题就是如何找到左右子树的分割点？
回忆一下 BST 的特性：
- 左子树的元素都比根元素小；
- 右子树的元素都比根元素大；
- BST 中不存在重复的元素；
结合上述性质：通过根节点与序列中元素的大小比较可以得到左右子树的分割点。
在这里插入图片描述三、105. 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。
本道题目要求构造一棵普通的二叉树，而非 BST。
代码语言：rust复制 前序遍历：根节点 --> 左子树 --> 右子树
中序遍历: 左子树 --> 根节点 --> 右子树从上述两个遍历序列中，大家应该已经发现分割左右子树的条件就藏在中序遍历中。
根据前序遍历得到根元素，再遍历中序遍历序列得到根元素的下标，从而分割左右子树。如果二叉树中存在重复元素，那么这种方案是行不通的，这也是此类型题目一个重要的条件。
在这里插入图片描述四、106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。
本题的解题思路与上一道题的解题思路如出一辙，所以正好借用本道题目介绍一下时间复杂度的优化。
上一题解题代码的耗时操作主要在于频繁地使用 shift、indexOf 和 slice。
对于 indexOf 操作，可以采用 HashTable 代替，这是经典的空间换时间的优化方式。
而对于 shift 和 slice，可以采用多指针记录下标来处理。这里的下标计算有点复杂，建议大家自己画一画遍历的过程，不然很难明白写法的推导过程。
在这里插入图片描述五、889. 根据前序和后序遍历构造二叉树
返回与给定的前序和后序遍历匹配的任何二叉树。pre 和 post 遍历中的值是不同的正整数。
还是老套路，先观察两个遍历序列：
代码语言：rust复制 前序遍历：根节点 --> 左子树 --> 右子树
后序遍历：左子树 --> 右子树 --> 根节点这不是熟悉的感觉啊，看来看去，根节点也不好将左右子树分割啊！?
现在，尝试展开左右子树：参考视频：传送门
代码语言：rust复制 前序遍历：根节点 --> (根节点 --> 左子树 --> 右子树) --> 右子树
后续遍历：(左子树 --> 右子树 --> 根节点) --> 右子树 --> 根节点是不是有点明朗了，再把左右根节点去掉，是不是发现根据左子树的根节点，可以将左右子树分割开呀。
代码语言：rust复制 前序遍历：(根节点 --> 左子树 --> 右子树) --> 右子树
后续遍历：(左子树 --> 右子树 --> 根节点) --> 右子树
在这里插入图片描述写在最后
算法作为计算机的基础学科，用 JavaScript 刷，一点也不丢人ε=ε=ε=┏(゜ロ゜;)┛。
本系列文章会分别给出一种算法的3种难度的总结篇（简单难度，中等难度以及困难难度）。在简单难度中，会介绍该算法的基本知识与实现，另外两个难度，着重讲解解题的思路。
如果本文对您有所帮助，可以点赞或者关注来鼓励博主。
