给定两个整数数组 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[0]是root
2.在inorder中找到preorder[0]的索引idx，索引之前的为root->left,中序遍历为inorder[1,idx-1] 索引之后为root->right,中序遍历为inorder[idx+1,end]
3.根据2中的索引位置，确定root->left的节点数量leftnum和root->right的节点数量rightnum
4.在preorder中确定左右子树的前序遍历，root->left的前序遍历为preorder[1,leftnum],root->right的前序遍历为preorder[leftnum+1,end]
5.处理好边界和迭代终止条件

解法1：

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size() == 0) return nullptr;TreeNode* root = new TreeNode(preorder[0]);return build(preorder, 0, preorder.size() - 1,inorder, 0, inorder.size() - 1);}TreeNode* build(vector<int>& preorder, int prestart, int preend,vector<int>& inorder, int instart, int inend){if(prestart > preend) return nullptr;int val = preorder[prestart];int idx = find(inorder.begin(), inorder.end(), val) - inorder.begin();int leftsize = idx - instart;TreeNode* root = new TreeNode(val);root->left = build(preorder, prestart+1, prestart+leftsize,inorder, instart, idx-1);root->right  = build(preorder, prestart+leftsize+1, preend,inorder, idx+1, inend);return root;}

解法2：从注释中应该可以看出来我调试了多少次*_*,思路没打开，主要是进行了vector的拷贝，导致内存占用很大，边界问题也没有搞的很清楚，导致有不少if判断，注释打开的话submit会超时超内存，关闭注释就可通过。

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size() == 0) return nullptr;TreeNode* root = new TreeNode(preorder[0]);vector<int>::iterator iter = find(inorder.begin(), inorder.end(), preorder[0]);int leftnodenum = iter - inorder.begin();int rightnodenum = inorder.end() - iter - 1;//cout << leftnodenum << " " << rightnodenum << endl;vector<int> leftpreorder, rightpreorder;if(leftnodenum > 0)leftpreorder.assign(preorder.begin()+1, preorder.begin()+leftnodenum+1);if(rightnodenum > 0)rightpreorder.assign(preorder.begin()+leftnodenum+1, preorder.end());/*cout << "leftpreorder: " ;printvec(leftpreorder);cout << "rightpreorder: ";printvec(rightpreorder);*//*vector<int> leftinorder, rightinorder;if(iter != inorder.begin())leftinorder.assign(inorder.begin(), iter+1);if(iter != inorder.end())rightinorder.assign(iter+1, inorder.end());/*cout << "leftinorder: ";printvec(leftinorder);cout << "rightinorder: ";printvec(rightinorder);*///return nullptr;root->left = buildTree(leftpreorder, leftinorder);root->right = buildTree(rightpreorder, rightinorder);return root;}