核心思想：分治法
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); } 2 已知中序、后序求先序： // 注意处理端点 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); } 两种 方式 差别 仅在 对于 根 位置 处理上
