例题10.2二叉树遍历（华科）

例题10.2二叉树遍历（华科）

关键字：二叉树构造、遍历二叉树

要点：通过给出的先序遍历序列和中序遍历序列要能构造出原本的二叉树来

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

struct TreeNode {
	char data;
	TreeNode* left;
	TreeNode* right;
	TreeNode(char x) :data(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(string strPreOrder, string strInOrder) {
	if (strPreOrder.size() == 0 || strInOrder.size() == 0)
		return nullptr;
	char x = strPreOrder[0];
	TreeNode* root = new TreeNode(x);
	int position = strInOrder.find(x);  //找到当前节点x在字符串中的下标
	root->left = buildTree(strPreOrder.substr(1, position), strInOrder.substr(0,position)); //substr(pos,len);
	root->right = buildTree(strPreOrder.substr(position + 1), strInOrder.substr(position + 1));
	return root;
}

void postOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	if (root->left != nullptr)
		postOrder(root->left);
	if (root->right != nullptr)
		postOrder(root->right);
	cout << root->data;
}

int main() {
	string strPreOrder,strInOrder;
	while (cin >> strPreOrder && cin >> strInOrder) {
		TreeNode* root = buildTree(strPreOrder, strInOrder);
		postOrder(root);
		cout << endl;
	}
	return 0;
}