一、前言
上一篇中介绍了如何采纳 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 种难度的总结篇(简略难度,中等难度以及艰难难度)。在简略难度中,会介绍该算法的基本知识与实现,另外两个难度,着重解说解题的思路。
如果本文对您有所帮忙,能够点赞或者关注来激励博主。