算法|算法:重建二叉树

算法|算法:重建二叉树

文章图片

算法|算法:重建二叉树

文章图片



重建二叉树输入某二叉树的前序遍历和中序遍历的结果 , 请构建该二叉树并返回其根节点 。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字 。
示例1

  • Input:preorder = [3920157
    inorder = [9315207

  • Output:[3920nullnull157

示例2
  • Input: preorder = [-1
    inorder = [-1

  • Output: [-1

限制0 <= 节点个数 <= 5000
方法一:递归思路
  • 前序遍历:【根节点 | 左子树 | 右子树】
  • 中序遍历:【左子树 | 根节点 | 右子树】
只要我们在中序遍历中定位到根节点 , 那么我们就可以分别知道左子树和右子树中的节点数目 。 由于同一颗子树的前序遍历和中序遍历的长度显然是相同的 , 因此我们就可以对应到前序遍历的结果中 , 对上述形式中的所有左右括号进行定位 。
这样 , 我们就知道了左子树的前序遍历和中序遍历结果 , 以及右子树的前序遍历和中序遍历结果 , 我们就可以递归地对构造出左子树和右子树 , 再将这两颗子树接到根节点的左右位置 。
细节
在中序遍历中对根节点进行定位时 , 一种简单的方法是直接扫描整个中序遍历的结果并找出根节点 , 但这样做的时间复杂度较高 。 我们可以考虑使用哈希表来帮助我们快速地定位根节点 。
对于哈希映射中的每个键值对 , 键表示一个元素(节点的值) , 值表示其在中序遍历中的出现位置 。 在构造二叉树的过程之前 , 我们可以对中序遍历的列表进行一遍扫描 , 就可以构造出这个哈希映射 。
在此后构造二叉树的过程中 , 我们就只需要 O(1)的时间对根节点进行定位了 。
代码如下:

复杂度分析
  • 时间复杂度:O(n) , 其中 n 是树中的节点个数 。
  • 空间复杂度:O(n) , 除去返回的答案需要的 O(n) 空间之外 , 我们还需要使用 O(n) 的空间存储哈希映射 , 以及 O(h)(其中 h 是树的高度)的空间表示递归时栈空间 。 这里 h < n , 所以总空间复杂度为 O(n) 。
方法二:迭代思路
  • 前序遍历 , 从根节点root开始 , 只要有左子节点 , 就一直会往左下方走 , 直到最左下角 。
  • 中序遍历 , 是从最左下角往上 , 如果碰到节点有右子节点 , 则会转向 。
算法
我们用一个栈和一个指针辅助进行二叉树的构造 。 初始时栈中存放了根节点(前序遍历的第一个节点) , 指针指向中序遍历的第一个节点;
我们依次枚举前序遍历中除了第一个节点以外的每个节点 。 如果 index 恰好指向栈顶节点 , 那么我们不断地弹出栈顶节点并向右移动 index , 并将当前节点作为最后一个弹出的节点的右儿子;如果 index 和栈顶节点不同 , 我们将当前节点作为栈顶节点的左儿子 。
无论是哪一种情况 , 我们最后都将当前的节点入栈 。
【算法|算法:重建二叉树】最后得到的二叉树即为答案 。
代码如下:

复杂度分析
  • 时间复杂度:O(n) , 其中 n 是树中的节点个数 。
  • 空间复杂度:O(n) , 除去返回的答案需要的 O(n) 空间之外 , 我们还需要使用 O(h)(其中 h 是树的高度)的空间存储栈 。 这里 h < n , 所以(在最坏情况下)总空间复杂度为 O(n) 。
写在最后本文内容出处是力扣官网 , 希望和大家一起刷算法 , 在后面的路上不变秃但是变强!
好兄弟可以点赞并关注我 , 全部都是干货 。