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