题目
题目链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
初步题解
先放代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// TreeNode* re = nullptr;
if(preorder.empty()){
return nullptr;
}
//根节点
TreeNode* root = new TreeNode(preorder[0]);
// root->val = inorder[0];
vector<int> lPreorder,rPreorder;
vector<int> lInorder,rInorder;
int midIndex = 0;
for(int i = 0; i<inorder.size() ; i++){
if(inorder[i]==preorder[0]){
midIndex = i;
break;
}
}
// 获取左右子树的结点数量
int leftSize = midIndex;
int rightSize = preorder.size() - midIndex - 1;
// 分开赋值
for(int i=0 ; i<midIndex ; i++){
lInorder.push_back(inorder[i]);
// lPreorder[i]=preorder[i];
}
for(int i=midIndex+1 ; i<inorder.size() ; i++){
rInorder.push_back(inorder[i]);
// lPreorder[i-midIndex-1]=preorder[i];
}
for(int i=1 ; i<leftSize+1 ; i++){
lPreorder.push_back(preorder[i]);
// lInorder[i-1] = inorder[i];
}
for(int i=leftSize+1 ; i<preorder.size() ; i++){
rPreorder.push_back(preorder[i]);
// rInorder[i-1] = inorder[i];
}
//左子树
root->left = buildTree(lPreorder,lInorder);
//右子树
root->right = buildTree(rPreorder,rInorder);
return root;
}
};
思路很简单，先序遍历时，根节点的值会被放在第一个。而中序遍历时，根节点的值刚好把左右子树全部的值分隔开，就是利用这一句话的思路做题。我们只要先按照先序遍历分隔开中序遍历为左子树和右子树的值，然后在分别对左右子树进行递归操作就可以了。
递归退出点的选择：返回的值是树的结点指针，也就是作为父节点的左右子结点来用。这样只要最后不满足条件时返回null就可以了。至于退出条件，就是传入的先序遍历（或后序遍历）所承载的数组为空就可以退出了。
但是这样做结果很慢：
而实际上比较快的只需要24ms，足足慢了10倍，必须要优化。
优化
存在两个优化点。第一个是每次都要搜索root节点在中序遍历中的位置，第二个是每次都要来回创建新的vector来存放中序遍历的左右子树再往下递归，这个创建vector并赋值的过程其实很耗时间。
-
针对一个点，可以创建一个全局的map来避免每次都查找，不然每一次递归都要寻找根节点的位置。
-
针对第二个点，选择传index，而不是重新赋值来做，这样节省了大量的时间。
优化后的代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
map<int,int> inorder_map;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for(int i=0;i<inorder.size();i++){
// 方便一下找到大小为i的元素在哪个位置了，省去了遍历浪费的时间
inorder_map[inorder[i]]=i;
}
TreeNode* root = new TreeNode;
root = Recur_buildTree(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
return root;
}
TreeNode* Recur_buildTree(vector<int>& preorder, vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end){
if(pre_start > pre_end || in_start > in_end){
return nullptr;
}
//根节点
TreeNode* root = new TreeNode(preorder[pre_start]);
int mid_index = inorder_map[preorder[pre_start]];
// 获取左子树的结点数量
int left_size = mid_index - in_start;
//左子树
root->left = Recur_buildTree(preorder, inorder, pre_start + 1, pre_start + left_size, in_start, in_start + left_size -1);
//右子树
root->right = Recur_buildTree(preorder, inorder, pre_start + left_size + 1, pre_end, mid_index+1, in_end);
return root;
}
};
优化后的速度：
