//输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x):val(x), left(NULL), right(NULL){}
};
void reConstructBinaryTreeFun(TreeNode *head, vector<int> pre, vector<int> vin)
{
if(pre.size() <= 1 && vin.size() <=1)//没有子节点了,结束
{
return ;
}
vector<int> vecLeftVin, vecLeftPre;
vector<int> vecRightVin, vecRightPre;
size_t vecLeftVin_size = 0;
vector<int>::iterator it;
//前序遍历的第一个(即pre[0])为根节点
it = find(vin.begin(), vin.end(), pre[0]); //找到根节点在中序遍历中的位置
head->val = pre[0];
//中序遍历根节点左边的,为左分支。
if(it != vin.begin())
{
head->left = new TreeNode( *(it-1) );//中序遍历中,根节点左边第一个为根的左节点。
vecLeftVin.assign(vin.begin(),it);//将中序遍历中根左边的部分放到新的vec中
vecLeftVin_size = vecLeftVin.size();//记录大小
vecLeftPre.assign(pre.begin()+1, pre.begin()+1+vecLeftVin_size);//将前序遍历中根左边的部分放到新的vec中
reConstructBinaryTreeFun(head->left,vecLeftPre, vecLeftVin);//继续递归分析
}
//中序遍历根节点右边的,为右分支。
if(it != vin.end()-1)
{
head->right = new TreeNode( *(it+1));//中序遍历中,根节点右边第一个为根的右节点。
vecRightVin.assign(it+1, vin.end()); //将中序遍历中根右边的部分放到新的vec中
size_t vecRightVin_size = vecRightVin.size();//记录大小
vecRightPre.assign(pre.end()-vecRightVin_size, pre.end());//将前序遍历中根右边的部分放到新的vec中
reConstructBinaryTreeFun(head->right, vecRightPre, vecRightVin);//继续递归分析
}
}
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
{
TreeNode * head ;
head = new TreeNode(pre[0]);
reConstructBinaryTreeFun(head,pre,vin);
return head;
}