朝阳百姓网免费发布信息,手机优化大师官网,ASP网站建设招聘,上海注册设计公司网站文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;递归 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本题涉及到的数据结构等内容… 文章目录 写在前面Tag题目来源题目解读解题思路方法一递归 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【递归】【迭代】【二叉树】 题目来源
105. 从前序与中序遍历序列构造二叉树 题目解读
给你一棵二叉树的前序和中序遍历得到的两个数组现在根据两个数组来构造二叉树。 解题思路
二叉树问题都可以使用递归和迭代两种方法来解决。
方法一递归
前言
首先回忆一下二叉树的前序和中序遍历过程。
二叉树的前序遍历过程
先遍历根节点接着递归遍历左子树最后递归遍历右子树。
二叉树的中序遍历过程
先递归遍历左子树接着遍历根节点最后递归遍历右子树。
在「递归」遍历子树的过程中我们也是将子树看成是一棵全新的树按照相应的顺序进行遍历。
思路
根据上述提到的前序遍历顺序可以将 preorder 数组分为三部分根、左子树、右子树。目前仅通过先序遍历的结果数组可以确定的是根节点值为 3。
中序遍历的结果数组可以分为三部分左子树、根、右子树。
只要我们在中序遍历的结果数组中定位出根节点那么就可以分别知道左子树和右子树的数目进而可以定位出左、右子树的边界即在数组中的范围。这样就知道了左子树的前序遍历和中序遍历结果以及右子树的前序遍历和中序遍历结果就可以递归地对构造出左子树和右子树再将这两棵子树接到根节点的左右位置。
在定位根节点的时候利用哈希表来记录各个节点在数组中的位置因为题目中事先说明了二叉树中节点的值不会出重复。哈希表中的键表示一个元素的值值表示该键表示的值在中序遍历数组中的位置。
算法
class Solution {
private:int pre_idx;unordered_mapint, int index_map;
public:TreeNode* slove(const vectorint preorder, const vectorint inorder, int in_left, int in_right) {if (in_left in_right) {return nullptr;}// 前序遍历中的根节点int root_val preorder[pre_idx];// 建立根节点TreeNode* root new TreeNode(root_val);// 在中序遍历中定位根节点int idx index_map[root_val];// 递归构建左子树需要左子树的先序、中序的边界root-left slove(preorder, inorder, in_left, idx - 1);root-right slove(preorder, inorder, idx 1, in_right);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int n inorder.size();pre_idx 0;// 构建哈希表快速定位根节点for (int i 0; i n; i) {index_map[inorder[i]] i;}return slove(preorder, inorder, 0, n-1);}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)其中 n n n 是树中的节点个数。
空间复杂度 O ( n ) O(n) O(n)。返回的答案需要 O ( n ) O(n) O(n) 空间通过不算作占用额外的空间哈希表占用的额外空间为 O ( n ) O(n) O(n)递归的栈空间最大为 O ( n ) O(n) O(n)。因此总的空间复杂度为 O ( n ) O(n) O(n)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
