本文共 1116 字，大约阅读时间需要 3 分钟。

核心思想：分治法

1 已知先序、中序 求后序

pre_pos 、  in_pos  、   post_pos  分别表示前中后 索引（初始均为0） 

int post[MAX];int in[MAX];int pre[MAX];

void to_post_tree(int pre_pos, int in_pos, int post_pos, int n){	  	int root;	if (n == 0)		return;	if (n == 1) {		post[post_pos] = pre[pre_pos];		return;	}	root = pre[pre_pos];	post[post_pos + n - 1] = root;//每次把当前处理区域的最后一个元素放入	int i;	for (i = 0; i < n; i++) {		if (in[in_pos + i] == root)			break;	}	int l_len, r_len;	l_len = i;	r_len = n - i - 1;	to_post_tree(pre_pos + 1, in_pos, post_pos,l_len);	to_post_tree(pre_pos + l_len+1, in_pos + l_len+1, post_pos + l_len, r_len);}

void to_pre_tree(int pre_pos, int in_pos, int post_pos, int n){	int root;	int i;	if (n == 0)		return;	if (n == 1) {		pre[pre_pos] = post[post_pos];		return;	}	root = post[post_pos+n - 1];	pre[pre_pos] = root;	for (i = 0; i < n; i++) {		if (in[in_pos+i] == root)			break;	}	int l_len, r_len;	l_len = i;//左子树长度 	r_len = n - l_len - 1;//右子树长度 	to_pre_tree(pre_pos+1, in_pos, post_pos, l_len);//递归处理左子树 与右子树 	to_pre_tree(pre_pos + l_len+1, in_pos + l_len + 1, post_pos + l_len, r_len);}

转载地址：http://yximi.baihongyu.com/