设计专业网站有哪些,网站建设哪家便,怎么做软文链接打开后是自定义网站,全省建设信息网站LeetCode 热题 100_从前序与中序遍历序列构造二叉树#xff08;47_105#xff09; 题目描述#xff1a;输入输出样例#xff1a;题解#xff1a;解题思路#xff1a;思路一#xff08;递归#xff09;#xff1a; 代码实现代码实现#xff08;思路一#xff08;递归… LeetCode 热题 100_从前序与中序遍历序列构造二叉树47_105 题目描述输入输出样例题解解题思路思路一递归 代码实现代码实现思路一递归以思路一为例进行调试 题目描述
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
输入输出样例
示例 1
输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
示例 2
输入: preorder [-1], inorder [-1] 输出: [-1]
提示 1 preorder.length 3000 inorder.length preorder.length -3000 preorder[i], inorder[i] 3000 preorder 和 inorder 均 无重复 元素 inorder 均出现在 preorder preorder 保证 为二叉树的前序遍历序列 inorder 保证 为二叉树的中序遍历序列
题解
解题思路
思路一递归
1、分析中序遍历和先序遍历的特点 先序遍历根 左 右 中序遍历: 左 根 右
① 我们可以通过先序遍历第一个结点来确定当前的根节点。 ② 通过preorder和inorder均无重复元素则可通过当前的根节点唯一确定中序遍历中当前根节点的位置从而将中序遍历序列划分为左 根 右三个区间。 ③ 通过中序遍历划分的左 根 右三个区间就可以将先序序列的左右区间也划分出来。 ④ 将划分的左右区间分别进行上述过程直至左右区间没有元素为止。 ⑤ 我们发现上述是一个递归的过程。 ⑥ 通过先序遍历第一个元素查找其在中序遍历中的位置是很耗费时间的我们可以建立一个哈希表来存储中序遍历元素值和下标的对应关系这样便能节省查找的时间。
2、复杂度分析 ① 时间复杂度O(n)n代表前序遍历或中序遍历中元素的个数。将中序遍历中的n个数据存入哈希表时间为O(n),将n个元素转换为二叉树O(n)。 ② 空间复杂度O(n)n代表前序遍历或中序遍历中元素的个数。将中序遍历中的n个数据存入哈希表所需空间为O(n)递归创建二叉树最坏的情况下为O(n)。
代码实现
代码实现思路一递归
class Solution {
private:unordered_mapint,int inorderVal_index;public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {//计算先序遍历数组和中序遍历数组的大小其实这两个是一样的int preLen preorder.size();int inLen inorder.size();//将中序遍历的元素和下标的对应关系存储到哈希表中for (int i 0; i inLen; i){inorderVal_index[inorder[i]]i;}//递归的构建二叉树包含先序和中序数组和其对应的范围下标return myBuildTree(preorder,inorder,0,preLen-1,0,inLen-1);}TreeNode* myBuildTree(vectorint preorder, vectorint inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right ){//如果区间元素为0则返回nullptr,也就是叶节点链接的nullptrif (preorder_leftpreorder_right){return nullptr;}//inorder_root代表中序遍历序列中根节点的下标int inorder_rootinorderVal_index[preorder[preorder_left]];//先序遍历第一个结点就是根节点创建根节点TreeNode *rootnew TreeNode(preorder[preorder_left]);//通过根在中序遍历的位置确定左区间的大小从而推出先序遍历的左右区间int size_left_subtreeinorder_root-inorder_left;//在左子区间递归的进行上述过程root-leftmyBuildTree(preorder,inorder,preorder_left1,preorder_leftsize_left_subtree,inorder_left,inorder_root-1);//在右子区间递归的进行上述过程root-rightmyBuildTree(preorder,inorder,preorder_leftsize_left_subtree1,preorder_right,inorder_root1,inorder_right);return root;}};以思路一为例进行调试
#includeiostream
#include vector
#include unordered_map
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};//中序遍历输出节点的值
void inorder_print(TreeNode *root){if (rootnullptr) return ;inorder_print(root-left);if(root!nullptr){coutroot-val ;}else{coutnull ;}inorder_print(root-right);
}//方法一
class Solution {
private:unordered_mapint,int inorderVal_index;public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {//计算先序遍历数组和中序遍历数组的大小其实这两个是一样的int preLen preorder.size();int inLen inorder.size();//将中序遍历的元素和下标的对应关系存储到哈希表中for (int i 0; i inLen; i){inorderVal_index[inorder[i]]i;}//递归的构建二叉树包含先序和中序数组和其对应的范围下标return myBuildTree(preorder,inorder,0,preLen-1,0,inLen-1);}TreeNode* myBuildTree(vectorint preorder, vectorint inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right ){//如果区间元素为0则返回nullptr,也就是叶节点链接的nullptrif (preorder_leftpreorder_right){return nullptr;}//inorder_root代表中序遍历序列中根节点的下标int inorder_rootinorderVal_index[preorder[preorder_left]];//先序遍历第一个结点就是根节点创建根节点TreeNode *rootnew TreeNode(preorder[preorder_left]);//通过根在中序遍历的位置确定左区间的大小从而推出先序遍历的左右区间int size_left_subtreeinorder_root-inorder_left;//在左子区间递归的进行上述过程root-leftmyBuildTree(preorder,inorder,preorder_left1,preorder_leftsize_left_subtree,inorder_left,inorder_root-1);//在右子区间递归的进行上述过程root-rightmyBuildTree(preorder,inorder,preorder_leftsize_left_subtree1,preorder_right,inorder_root1,inorder_right);return root;}};int main(int argc, char const *argv[])
{//前序遍历和中序遍历vectorint preorder{3,9,20,15,7};vectorint inorder{9,3,15,20,7};//通过先序遍历和中序遍历构造二叉树Solution s;TreeNode *root s.buildTree(preorder,inorder);//中序遍历输出构造的二叉树inorder_print(root);return 0;
}
LeetCode 热题 100_从前序与中序遍历序列构造二叉树47_105)原题链接 欢迎大家和我沟通交流(✿◠‿◠)
