二叉树重建【转自北大ACM】

二叉树重建
二叉树的遍历学列：先序序列，中序序列，后序序列，逆先序序列，逆后续序列
只要有一个中序序列再加上另一个序列就可唯一地重建原来二叉树。

可到这里测试下：http://acm.pku.edu.cn/JudgeOnline/problem?id=2255

#include <iostream>
using namespace std;

typedef char Type;
typedef struct Node
{
      Type data;
      Node *lc, *rc;
      Node(Type e='\0') : data(e) {}
}Node;

Node* Rebuild(Node *FirstArr[], Node *MidArr[], int n)
{
      if(n<1) return NULL;
      if(n==1) {
            FirstArr[0]->lc = FirstArr[0]->rc = NULL;
            return FirstArr[0];
      }
      Node *head = FirstArr[0];
      int i=0, len = 0;
      for(i=0, len=0; head != MidArr[i] && i<n; i++)
      {
            len++;
      }
      head->lc = Rebuild(FirstArr+1, MidArr, len);
      head->rc = Rebuild(FirstArr+1+len, MidArr+1+len, n-1-len);
      return head;
}

void postOrder(Node *head)
{
      if(head){     
            postOrder(head->lc);
            postOrder(head->rc);
            printf("%c\t", head->data);
      }
}

int main()
{
      const int n = 7;
      Node *FirstArr[n], *MidArr[n];
      Node node[n] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
      int f[] = {0,1,2,3,4,5,6}; // 先序序列
      int m[] = {2,1,4,3,0,5,6}; // 中序序列
      for(int i=0; i<n; i++)
      {
            FirstArr[i] = &node[ f[i] ];
            MidArr[i] = &node[ m[i] ];
      }

      Node *head = Rebuild(FirstArr, MidArr, n);
      postOrder(head); // 后序序列
      printf("\n");
      return 0;
}