题解 | #二叉树遍历#

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

struct TreeNode {
	char data;
	TreeNode* leftchild;
	TreeNode* rightchild;
};

void Postorder(TreeNode* t) {
	if (t == NULL) {
		return;
	}
	else {
		Postorder(t->leftchild);
		Postorder(t->rightchild);
		cout << t->data;
		return;
	}

}



TreeNode * BuildTree(string pre,string mid) {  //利用先序遍历来建树的原理
	if (0 == pre.size()) 
		return NULL;
	else {
		TreeNode* p = new TreeNode; 
		p->data = pre[0];
		//拿根来切割中序序列
		int pos = mid.find(pre[0]);  //找到中序序列中的下标
		p->leftchild = BuildTree(pre.substr(1, pos),mid.substr(0,pos) ); //将先序切割
		p->rightchild = BuildTree(pre.substr(pos + 1), mid.substr(pos + 1));
		return p;
	}


}

int main() {
	string pre,in;
	while (cin >> pre) {
		cin >> in;
		TreeNode * root;
		root = BuildTree(pre,in);
		Postorder(root);
		cout << endl;
	}
}