OJ中的1561编程题,来自北邮的二叉树确定问题,即由前序遍历序列和中序遍历序列来输出后序遍历系列

思考关于题解中的利用前序序列构造后序二叉树来完成,题中主要依赖于递归;那么我在想是否可以利用后序遍历序列和中序遍历序列去输出前序遍历序列呢?答案当然是可以的,不过在处理过程中是有差异的.

#include<iostream>
#include<string>
#include<unordered_map> 
using namespace std; 

//前序找到根节点索引
int preIndex;

//建立后序二叉树
void buildPostTree(const string &preorder,const string &inorder,int inStart,int inEnd,unordered_map<char,int> &inMap){
	if(inStart>inEnd)	return;
	char root=preorder[preIndex++];
	//拿到中序的根节点下标 
	int rootIndex=inMap[root];
	//建立后序遍历左子树
	buildPostTree(preorder,inorder,inStart,rootIndex-1,inMap);
	//建立后序遍历右子树
	buildPostTree(preorder,inorder,rootIndex+1,inEnd,inMap);
	//输出根节点
	cout<<root;
} 

int main(){
	string preorder,inorder;
	while(cin>>preorder>>inorder){
		preIndex=0;
		unordered_map<char,int> inMap;
		for(int i=0;i<inorder.size();i++)	inMap[inorder[i]]=i;
		buildPostTree(preorder,inorder,0,inorder.size()-1,inMap);
		c...