题目
链接：leetcode链接
思路分析
前序遍历的顺序是：根 + 左子树 + 右子树
中序遍历的顺序是： 左子树 + 根 + 右子树
所以，我们可以通过前序遍历获得二叉树的根
可以通过中序遍历去分割二叉树，将二叉树分割成 左子树 根 右子树
然后递归操作即可。
遍历前序序列，前序序列中的每一个元素都是一颗子树的根节点
所以，我们需要一个变量i来遍历前序序列，注意，在递归中，我们需要引用或者指针来传递该参数
找到根节点之后，在中序遍历中去寻找这个根节点，就可以将中序遍历分成三段了。
然后递归调用即可。
注意：有一点比较坑，就是如何去处理空树，当我们要分割后的区间的长度为0的时候就是空树，在具体代码中，我们采用了区间的起始下标和结尾下标
当 起始下标 > 结尾下标 的时候，就出现了空树，返回nullptr即可
代码
TreeNode* build(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend){if(inbegin > inend)return nullptr;TreeNode* root = new TreeNode(preorder[prei]);int begin = inbegin,end = inend;int rooti = 0;while(begin <= end){if(inorder[begin] == root->val){rooti = begin;break;}begin++;}prei++;root->left = build(preorder,inorder,prei,inbegin,rooti-1);root->right = build(preorder,inorder,prei,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i = 0;return build(preorder,inorder,i,0,inorder.size() - 1);}
变式题
题目：利用中序序列和后序序列构造二叉树
链接：leetcode链接
思路分析
和上面一样，思路大致相同
后序遍历找根（根在后面）
中序遍历分割子树
后序遍历的顺序是 左子树 + 右子树 + 根
与上面不同的是，
- 我们需要从后向前遍历后序遍历，i需要一直–
- 我们在构建好根节点之后，我们需要接着构造右子树，而并非左子树。
其余与上面几乎相同
代码
TreeNode* build(vector<int>& inorder,vector<int>& postorder,int& posti,int inbegin,int inend){if(inbegin > inend)return nullptr;TreeNode* root = new TreeNode(postorder[posti]);//后序遍历找根int begin = inbegin,end = inend;int rooti = 0;while(begin <= end)//中序遍历分割{if(inorder[begin] == root->val){rooti = begin;}begin++;}if(begin > end){cout << "很抱歉，中序序列和后序序列不匹配" << endl;exit(1);}posti--;root->right = build(inorder,postorder,posti,rooti+1,inend);root->left = build(inorder,postorder,posti,inbegin,rooti-1);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i = postorder.size() - 1;return build(inorder,postorder,i,0,inorder.size() - 1);}
