题解 | #二叉树遍历#

//土尔逊Torson 编写于2023/06/09
#define _CRT_SECURE_NO_WARNINGS
#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;
		//拿根去切割中序
		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");
	}
}
// 64 位输出请用 printf("%lld")