剑指offer——重建二叉树

因为前序遍历的第一个数为二叉树的根结点，二中序遍历根结点将二叉树分为左子树和右子树，这样就可以进行递归运算

solution.h

#include<iostream>#include<vector>using namespace std;/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */  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);};Solution.cpp
  TreeNode* Solution::reConstructBinaryTree(vector<int> pre,vector<int> vin){  		TreeNode* root=new TreeNode(pre.front());	vector<int> left_pre,left_vin,right_pre,right_vin;	//分别为左子树的前序遍历和中序遍历，以及是右子树的前序遍历和中序遍历	vector<int>::iterator iter_vin=vin.begin();		vector<int>::iterator iter_pre=pre.begin()+1;//分别为前序遍历和中序遍历的迭代器	if(vin.front()==pre.front())			//如果中序遍历根结点左边没有值	{		root->left=NULL;		//左子树直接为NULL	}	else	{	while(*iter_vin!=pre.front())		//把中序遍历到根结点之前的数都放入左子树的中序遍历中，同时存放右子树的前序遍历	{		left_vin.push_back(*iter_vin);		//左子树的中序遍历		left_pre.push_back(*iter_pre);		//左子树的中序遍历		iter_vin++;		iter_pre++;	}		root->left=reConstructBinaryTree(left_pre,left_vin);	//生成左子树	}	/*前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，	1 pre	247,3568vin	472,5386......*/	if(iter_pre==pre.end())			//如果根结点右边没有值，即前序遍历的迭代器，已经指向原值的末尾	{		root->right=NULL;				}	else	{		right_pre.assign(iter_pre,pre.end());				//vector的函数 assign，直接通过迭代器赋值		right_vin.assign(iter_vin+1,vin.end());		root->right=reConstructBinaryTree(right_pre,right_vin);	//生成右子树	}	return root;}main.cpp
#include<iostream>#include"Solution.h"using namespace std;/*题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。思路：因为前序遍历的第一个数为二叉树的根结点，二中序遍历根结点将二叉树分为左子树和右子树，这样就可以进行递归运算*/int main(){					int p[]={1,2,4,7,3,5,6,8};	int count=sizeof(p)/sizeof(int);	vector<int> pre(p,p+count);	int v[]={4,7,2,1,5,3,8,6};			vector<int> vin(v,v+count);		Solution s;	s.reConstructBinaryTree(pre,vin);	return 0;}