题目：重建二叉树
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
题目知识：
首先看题目应该最先看到的是这个几个关键点：1、二叉树，2、二叉树的前中后三种遍历。
先序遍历：遍历规则 根-左-右
中序遍历：遍历规则 左-根-右
后序遍历：遍历规则 左-右-根
接下来的排序：
先序遍历：ABCDEFGHK
中序遍历：BDCAEHGKF
后序遍历：DCBHKGFEA
先说中序遍历，先序遍历的规则是
左根右此时A是根节点，遍历A的左子树；
A的左子树存在，找到B，此时B看做根节点，遍历B的左子树；
B的左子树不存在，返回B，根据【左根右】的遍历规则，记录B，遍历B的右子树；
B的右子树存在，找到C，此时C看做根节点，遍历C的左子树；
C的左子树存在，找到D，由于D是叶子节点，无左子树，记录D，无右子树，返回C，根据【左根右】的遍历规则，记录C，遍历C的右子树；
C的右子树不存在，返回B，B的右子树遍历完，返回A；
至此，A的左子树遍历完毕，根据【左根右】的遍历规则，记录A，遍历A的右子树；
A的右子树存在，找到E，此时E看做根节点，遍历E的左子树；
E的左子树不存在，返回E，根据【左根右】的遍历规则，记录E，遍历E的右子树；
E的右子树存在，找到F，此时F看做根节点，遍历F的左子树；
F的左子树存在，找到G，此时G看做根节点，遍历G的左子树；
G的左子树存在，找到H，由于H是叶子节点，无左子树，记录H，无右子树，返回G，根据【左根右】的遍历规则，记录G，遍历G的右子树；
G的右子树存在，找到K，由于K是叶子节点，无左子树，记录K，无右子树，返回G，根据【左根右】的遍历规则，记录F，遍历F的右子树；
F的右子树不存在，返回F，E的右子树遍历完毕，返回A；
至此，A的右子树也遍历完毕；
那么接下来的前序和后序遍历类似的方式遍历。
题目分析
已知当知道先序和中序遍历的序列，或者知道中序和后序遍历序列时我们可以唯一确定一个二叉树，当只知道先序和后序的时候我们不能确定唯一的一棵树。
那我们先联系这样一个题目：
已知先序序列：ABCDEFGH,中序序列：BDCEAFHG,求出最终的序列来。
首先，先序和中序的遍历规则分别是根左右和左根右,那么我们可以知道此序列的根节点是A，在中序序列中，BDCE是A的左子树，FHG是A的右子树。
于是先序遍历也就分成这样的
而B又在先序遍历中是A左子树的根节点，再回到中序遍历中B是A座子树的根节点，那么DCE就是B的右子树，那么此时的图就变成了
那么我们接下来在看CDE，看先序遍历知道C是CDE的根节点，再根据中序遍历DCE知道D是C的左叶子节点，E是C的有叶子节点，那么此时我们的整个左子树完成了。
我们同样对右子树进行操作，在先序中右子树的顺序是：FGH，那么此右子树的根节点是F，再看中序的顺序是：FHG，F是根节点，那HG是F的右子树
再看先序遍历发现接下来的根节点是G，那么F的右子树节点是G，再看中序遍历的结果HG，H是G的左子树。
接下来
我们知道中序遍历：CEDFBAHG，后序遍历：EFDCBHGA
我们知道：
1、根据后序遍历知道此二叉树的根节点是A，那么在中序遍历中我们就可以分成左子树：CEDFB，右子树HG。
2、先看左子树的后序：EFDCB，我们知道左子树的根节点是B，再到中序CEDFB中我们知道。CEDF是B的左子树。
3、后序：EFDC，知道B的左子树的根节点是C，，而在中序CEDF中我们知道EDF是C的右子树
4、后序：EFD，知道C的右子树的根节点是D，而在中序EDF中我们知道E和F分别是D的左叶子节点和有叶子结点
5、中序：HG，我们知道是A的右子树，后序中HGA，说明A的右子树的根节点是G。
6、中序遍历中是HG，说明H是G的左叶子节点
综上所述，我们可以知道从遍历中获取整个二叉树的方法
题目代码：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size() != vin.size()||pre.size() == 0 || vin.size() == 0) return NULL;
else{
TreeNode* resNode = createTreeNodeHelper(pre,vin,0,0,vin.size()-1);
return resNode;
}
}
TreeNode* createTreeNodeHelper(vector<int> pre, vector<int> vin,int preRootPos,int vinLeft,int vinRight){
// pre 前序 vin 中序 preRootPos 前序根节点位置 vinLeft 中序左边界 vinRight 中序右边界
int vinRootPos,rootVal;
rootVal = pre[preRootPos];//前序遍历中根节点位置的值
if(vinLeft>vinRight) return NULL;
for(int i = vinLeft; i<=vinRight;i++){
if(vin[i] == rootVal)
vinRootPos = i; //根据根节点找到中序中根节点的位置vinRootPos,
}
int leftLen = vinRootPos - vinLeft;
TreeNode* resRoot = new TreeNode(rootVal);
resRoot->left = createTreeNodeHelper(pre,vin,preRootPos+1,vinLeft,vinRootPos-1);
resRoot->right = createTreeNodeHelper(pre,vin,preRootPos+leftLen+1,vinRootPos + 1, vinRight);
return resRoot;
}
};
通过迭代的方式，不断查找。
