題目描述：

給定兩個整數數組 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)原題鏈接
歡迎大家和我溝通交流(????)