题解 | 二叉树遍历

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

//构建一个结构体用来表示一个树的节点 
struct node{
	char value;
	struct node * left = NULL;
	struct node * right = NULL;
};

//建立一个函数返回特定的节点在序列中的下标
int searchInSeries(string s,char ch){
	int n = s.length();
	for(int i = 0;i<n;i++){
		if(s[i]==ch){
			return i;
		}
	}
	return -1;	//如果执行到这里，肯定出错了
}

//构建 一颗树(根节点，前序遍历，中序遍历，左起范围，右起范围)
void createTree(struct node* root,string s1,string s2,int l, int r){
	if(root==NULL) return;
	if(l>=r) return;
	char core = root->value;
	int index1 = searchInSeries(s2,core);	//中序遍历index
	int index2 = searchInSeries(s1,core);	//前序遍历index
	//如果我的左侧还有机会是一棵树
	if(index1>l){
		int dk = index2;
		for(int i = index2;i<s1.length();i++){
			dk = searchInSeries(s2,s1[i]);
			if(dk<index1){
				break;
			}
		}
		char c = s2[dk];
		struct node* newNode = new struct node;
		newNode->value = c;
		root->left = newNode;
		//继续以其作为根节点访问下一层
		createTree(root->left,s1,s2,l,index1-1);
	}
	//如果我的右侧也有机会是一棵树
	if(index1<r){
		int dk = index2;
		for(int i = index2;i<s1.length();i++){
			dk = searchInSeries(s2,s1[i]);
			if(dk>index1){
				break;
			}
		}
		char c = s2[dk];
		struct node* newNode = new struct node;
		newNode->value = c;
		root->right = newNode;
		//继续以其作为根节点访问下一层
		createTree(root->right,s1,s2,index1+1,r);
	}
}

//按照后序遍历遍历一棵树(先左后右然后根节点)
void travelTree(struct node* root){
	if(root==NULL) return;
	if(root->left!=NULL){
		travelTree(root->left);
	}
	if(root->right!=NULL){
		travelTree(root->right);
	}
	if(root!=NULL){
		cout<<root->value;
	}
}

/*
 *二叉树遍历
 * */
int main(){
	string s1,s2;	//二叉树的前序和中序遍历
	while(cin>>s1>>s2){
		int n1 = s1.length();
		int n2 = s2.length();
		//首先从前序遍历入手，构建一颗二叉树
		struct node root;
		root.value = s1[0];
		//构建树
		createTree(&root,s1,s2,0,n1-1);
		travelTree(&root);
        cout<<endl;
	}
}