原题LeetCode链接：剑指Offer 07. 重建二叉树
题目：剑指Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下二叉树
3
/ \
9 20
/ \
15 7
思路
给出两个遍历序列来建二叉树这种题目解决方法几乎是一致的。
1.前序遍历序列的第一个元素是整棵树的根节点
2.在中序遍历中找到根节点，它的左边就是左子树的元素，右边就是右子树的元素
3.计算出左子树和右子树各有多少节点，然后继续在先序遍历中寻找左右子树的根节点，递归执行下去，直到完成。
C++代码
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}
//类似建树的题目都需要另外写一个函数
//preL,PreR,inL,inR分别是前序遍历起始和结束位置、后序遍历起始和结束位置
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR){
if(preL > preR || inL > inR) return NULL;
TreeNode* root = new TreeNode(preorder[preL]);
int i;
for(i = inL; i < inR; i++){
if(preorder[preL] == inorder[i])
break;
}
root->left = build(preorder, inorder, preL+1, preL + i - inL, inL, i-1);
root->right = build(preorder, inorder, preL+i-inL+1, preR, i+1, inR);
return root;
}
};
复杂度分析
时间复杂度：O(n).每个结点都要经历一遍建树过程
空间复杂度：O(n).存储整棵树
