从前序和中序遍历中重建二叉树

build_post.cpp

#include <string.h>
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>

void build_post(const char *pre, const char *in, const int n, char *post) {
	int left_len = strchr(in, pre[0]) - in;
	if (n <= 0) {
		return;
	}

	build_post(pre+1, in, left_len,post);
	build_post(pre+left_len+1, in+left_len+1, n-left_len-1, post+left_len);
	post[n-1] = pre[0];
}

#define MAX 64

void build_post_test() {
	char pre[MAX] = {0};
	char in[MAX] = {0};
	char post[MAX] = {0};

	int n;
	scanf("%s %s",pre, in);
	n = strlen(pre);
	build_post(pre,in,n,post);
	printf("%s\n",post);
}

typedef char elem_t;
typedef struct treeNode {
	elem_t elem;
	struct treeNode *left;
	struct treeNode *right;
} treeNode;

void rebuild(const char *pre, const char *in, int n, treeNode ** root) {
	int left_len;
	if (n <= 0 || pre == NULL || in == NULL) {
		return;
	}

	(*root) = (treeNode *)malloc(sizeof(treeNode));

	(*root)->elem = *pre;
	(*root)->left = NULL;
	(*root)->right = NULL;

	left_len = strchr(in, pre[0])-in;
	rebuild(pre+1, in, left_len, &((*root)->left));
	rebuild(pre+left_len+1, in+left_len+1, n-left_len, &((*root)->right));
}

void print_post_order(treeNode *node) {
	if (node == NULL) {
		return;
	}
	print_post_order(node->left);
	print_post_order(node->right);
	printf("%c", node->elem);
}

void rebuild_test() {
	char pre[MAX] = {0};
	char in[MAX] = {0};
	
	int n;
	scanf("%s %s",pre, in);
	n = strlen(pre);
	
	treeNode *root = NULL;

	rebuild(pre,in,n,&root);
	print_post_order(root);
}

int main() {
	build_post_test();

	rebuild_test();
	return 0;
}