Python教程

树-剑指offer7重建二叉树-中等-20210810python

本文主要是介绍树-剑指offer7重建二叉树-中等-20210810python,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

树-剑指offer7重建二叉树-中等-20210810

1. 题目描述

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中==都不含重复的数字==。
二叉树

示例

示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

2. 题目解答

2.1 递归

主要思路:

  • 前序遍历的首元素为树的根节点node的值。只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目

在中序遍历中搜索根节点node的索引 ,可将 中序遍历 划分为 [ 左子树 | 根节点 | 右子树 ]
根据中序遍历中的左 / 右子树的节点数量,可将 前序遍历 划分为 [ 根节点 | 左子树 | 右子树 ]

可确定 三个节点 :1.树的根节点、2.左子树根节点、3.右子树根节点。

  • 这样以来,我们就知道了左子树的前序遍历和中序遍历结果,以及右子树的前序遍历和中序遍历结果,我们就可以递归地对构造出左子树和右子树,再将这两颗子树接到根节点的左右位置。

在中序遍历中对根节点进行定位时,一种简单的方法是直接扫描整个中序遍历的结果并找出根节点,但这样做的时间复杂度较高。我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对,键表示一个元素(节点的值),值表示其在中序遍历中的出现位置。在构造二叉树的过程之前,我们可以对中序遍历的列表进行一遍扫描,就可以构造出这个哈希映射。在此后构造二叉树的过程中,我们就只需要 O(1) 的时间对根节点进行定位了。

时间复杂度:O(n),其中 n是树中的节点个数。

空间复杂度:O(n),除去返回的答案需要的 O(n) 空间之外,还需要使用 O(n)的空间存储哈希映射,以及 O(h)(其中 h是树的高度)的空间表示递归时栈空间。这里 h < n,所以总空间复杂度为 O(n)。


2.2 官方题解


2.3 评论较优解答


3. 错解

错误历程一:



3. 错解

错误历程一:


                    
这篇关于树-剑指offer7重建二叉树-中等-20210810python的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!