题解 | #二叉树遍历#

#include<iostream>
#include<string>

using namespace std;

//定义二叉树结构体
struct TreeNode{
	char data;
	TreeNode* leftChild;
	TreeNode* rightChild;
	TreeNode(){}
	TreeNode(char c):data(c),leftChild(nullptr),rightChild(nullptr){}	
};

//创建一棵二叉树
TreeNode* Build(string preOrder,string inOrder){
	if(preOrder.size() == 0){    //表明这是一棵空数
		return nullptr;
	}
	//否则就需要一个字符构成一个新的节点
	//根据先序遍历的特点，这棵树的根节点一定为先序遍历的第一个元素，也即preOrder[0]
	char c = preOrder[0];
	TreeNode* root = new TreeNode(c);    //通过构造函数构造一个根节点
	//通过递归将左子树和右子树构造出来
	//那么就需要确定左子树和右子树中的前序和中序序列
	//这就需要通过根节点在中序遍历中的位置将序列一分为二
	int position = inOrder.find(c);    //找出在中序遍历中的位置
	root->leftChild = Build(preOrder.substr(1,position),inOrder.substr(0,position));   //建立左子树
	root->rightChild = Build(preOrder.substr(position + 1),inOrder.substr(position + 1));
	return root;
}

//定义后序遍历的方法
void PostOrder(TreeNode* root){
	if(root == nullptr){
		return ;
	}
	PostOrder(root->leftChild);
	PostOrder(root->rightChild);
	printf("%c",root->data);
}



int main() {
	string preOrder;
	string inOrder;
	while(cin >> preOrder >> inOrder){
		TreeNode* root = Build(preOrder,inOrder);
		PostOrder(root);   //后续遍历这棵树
		printf("\n");
	}
	return 0;
}