题解 | #二叉树遍历#

#include<cstdio>
#include<string>
using namespace std;
struct TreeNode{
	char data;
	TreeNode *leftChild;
	TreeNode *rightChild;
	};
TreeNode * rebuild(string preOrder,string inOrder){
	//rebuild的返回表示子树根节点的地址
	if(preOrder.size() == 0){
		return NULL;
		}
	else{
		//从先序中确定根
		char rootdata = preOrder[0];
		TreeNode *pNewNode  = new TreeNode;
		pNewNode->data = rootdata;
		//再用根去切割中序
		inOrder.find(rootdata);
		int pos = inOrder.find(rootdata);//pos是根在中序序列中出现的下标
		//preOrder.substr(1,pos);将preOrder切割，取出下标1开始，长度为pos的子串
		//preOrder.substr(pos+1); 将preOrder切割，取出下标pos+1开始，到结束位置的子串
		//inOrder.substr(0,pos);
		//inOrder.substr(pos+1);
		pNewNode->leftChild = rebuild(preOrder.substr(1,pos), inOrder.substr(0,pos));
		pNewNode->rightChild = rebuild(preOrder.substr(pos+1), inOrder.substr(pos+1));
		return pNewNode;
		}
	}
void postOrder(TreeNode *root){
	if(root == NULL){
		return;
		}
	postOrder(root->leftChild);
	postOrder(root->rightChild);
	printf("%c",root->data);
	}
int main(){
	char preOrder[30];
	char inOrder[30];
	while(scanf("%s%s",preOrder,inOrder) != EOF){
		TreeNode * root;
		root = rebuild(preOrder,inOrder);
		postOrder(root);
		printf("\n");
		}
	}