输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的后序遍历序列。 （本题可以直接输出来，不用先还原出二叉树）

答案： 递归的简单应用，前序遍历的根在最前面，在中序遍历里找到那个数，然后前序序列和中序序列的分解成为两部分，对这两部分在递归即可。可以直接生成后续遍历的序列，而不用重构出这棵树。

#include <iostream>      using namespace std;      int pre[1024],post[1024],in[1024];      bool can(int *pre,int *in,int *post,int fpre,int fin,int fpost,int len) {  int i;          if (len <= 0) {                  return true;          }          for (i = 0; i < len; ++i) {                  if (pre[fpre] == in[fin + i]) {                          break;                  }          }          if (i >= len) {                  return false;          }          if (!can(pre,in,post,fpre + 1,fin,fpost,i)) {                  return false;          }          if (!can(pre,in,post,fpre + i + 1,fin + i + 1, fpost + i,len - i - 1)) {                  return false;          }          post[fpost + len - 1] = pre[fpre];          return true;  }          int main() {  int i,n;          while (scanf("%d",&n) != EOF) {                  for (i = 0; i < n; ++i) {                          scanf("%d",pre + i);                  }                  for (i = 0; i < n; ++i) {                          scanf("%d", in + i);                  }                  if (can(pre,in,post,0,0,0,n)) {                          for (i = 0; i < n; ++i) {                                  printf("%d ",post[i]);                          }                          puts("");                  }                  else {                          puts("No");                  }          }          return 0;  }