LeetCode 热题 100_从前序与中序遍历序列构造二叉树（47_105_中等_C++）(二叉树；递归)

题目描述：

给定两个整数数组 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_map<int,int> inorderVal_index;public:TreeNode* buildTree(vector<int>& preorder, vector<int>& 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(vector<int>& preorder, vector<int>& inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right ){//如果区间元素为0则返回nullptr,也就是叶节点链接的nullptrif (preorder_left>preorder_right){return nullptr;}//inorder_root代表中序遍历序列中根节点的下标int inorder_root=inorderVal_index[preorder[preorder_left]];//先序遍历第一个结点就是根节点，创建根节点TreeNode *root=new TreeNode(preorder[preorder_left]);//通过根在中序遍历的位置确定左区间的大小，从而推出先序遍历的左右区间int size_left_subtree=inorder_root-inorder_left;//在左子区间递归的进行上述过程root->left=myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);//在右子区间递归的进行上述过程root->right=myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);return root;}};

以思路一为例进行调试

#include<iostream>
#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 (root==nullptr) return ;inorder_print(root->left);if(root!=nullptr){cout<<root->val<<" ";}else{cout<<"null ";}inorder_print(root->right);
}//方法一：
class Solution {
private:unordered_map<int,int> inorderVal_index;public:TreeNode* buildTree(vector<int>& preorder, vector<int>& 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(vector<int>& preorder, vector<int>& inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right ){//如果区间元素为0则返回nullptr,也就是叶节点链接的nullptrif (preorder_left>preorder_right){return nullptr;}//inorder_root代表中序遍历序列中根节点的下标int inorder_root=inorderVal_index[preorder[preorder_left]];//先序遍历第一个结点就是根节点，创建根节点TreeNode *root=new TreeNode(preorder[preorder_left]);//通过根在中序遍历的位置确定左区间的大小，从而推出先序遍历的左右区间int size_left_subtree=inorder_root-inorder_left;//在左子区间递归的进行上述过程root->left=myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);//在右子区间递归的进行上述过程root->right=myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);return root;}};int main(int argc, char const *argv[])
{//前序遍历和中序遍历vector<int> preorder={3,9,20,15,7};vector<int> inorder={9,3,15,20,7};//通过先序遍历和中序遍历构造二叉树Solution s;TreeNode *root= s.buildTree(preorder,inorder);//中序遍历输出构造的二叉树inorder_print(root);return 0;
}

LeetCode 热题 100_从前序与中序遍历序列构造二叉树（47_105)原题链接
欢迎大家和我沟通交流(✿◠‿◠)