题解 | #二叉树遍历#

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


//例题10.2 二叉树遍历 华中科技大学复试上机题
struct TreeNode {
	char data;
	TreeNode* leftChild;
	TreeNode* rightChild;
	TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL){}
};

TreeNode* Build(string str1, string str2) {
	if (str1.size() == 0) {
		return NULL;
	}
	char c = str1[0];
	int pos = str2.find(c);
	TreeNode* root = new TreeNode(c);
	root->leftChild = Build(str1.substr(1, pos), str2.substr(0, pos));
	root->rightChild = Build(str1.substr(pos + 1), str2.substr(pos + 1));

	return root;
}

void postOrder(TreeNode* root) {
	if (root == NULL) {
		return;
	}
	postOrder(root->leftChild);
	postOrder(root->rightChild);
	cout << root->data;
}


int main()
{
	string s1, s2;
	while (getline(cin, s1)) {
		getline(cin, s2);
		TreeNode* root = Build(s1, s2);
		postOrder(root);
		cout << endl;
	}

	return 0;
}