so true

#include <iostream>
#include <assert.h>
using namespace std;
 
#define FIRST "ABCDEFGH"
#define MIDDLE "CBEDAGHF"

//function description: get the last-root order from the first-root order and middle-root order
//the recursive form of the needed function as follows.
char* getFirstRootOrder(const char* first,const char* middle,int len,char* last){
 if(0==len)return last+1;//return the position where the character has been filled.
 char root=*first;
 int root_pos=-1;
 while(middle[++root_pos]!=root);//get the position in the middle-order string.
 *last=root;
 char * rev=getFirstRootOrder(&first[root_pos+1],&middle[root_pos+1],len-root_pos-1,last-1);
 rev=getFirstRootOrder(first+1,middle,root_pos,rev-1);//'rev-1' is a position that any character hasn't filled.
 return rev;
}

//the non-recursive form of the needed function as follows.
struct Node{
 const char* f;//the pointer of the first-order string
 const char* m;//the pointer of the middle-order string
 int len;//the length of the processing string
};

void getFRONR(const char* first, const char* middle,char* last){
 assert(first!=NULL && middle!=NULL);
 assert(strlen(first)==strlen(middle));

 int len=strlen(first);
 const char *pf=first;
 const char *pm=middle;

 Node *pstack=new Node[len];
 int index=0;
 int I_pos=len-1;

 do{
  while(len!=0){
   int root_pos=0;
   while(pm[root_pos++]!=*pf);
   last[I_pos--]=*pf;
   
   //push operation of the stack
   //the left-hand sub-tree is pushed into the stack
   pstack[index].len=root_pos-1;
   pstack[index].f=pf+1;
   pstack[index++].m=pm;

   //update the new right-hand sub-tree
   len=len-root_pos;
   pf=pf+root_pos;
   pm=pm+root_pos;
  }
  if(index>0){//pop operation of the stack
   len=pstack[--index].len;
   pf=pstack[index].f;
   pm=pstack[index].m;
  }
 }while(index>0 || len!=0);
 delete [] pstack;
}

void main(){
 int len=strlen(FIRST);
 assert(strlen(MIDDLE)==len);
 char *first=new char[len+1];
 strcpy(first,FIRST);
 char *middle=new char[len+1];
 strcpy(middle,MIDDLE);
 char *last=new char[len+1];
 memset(last,0,len+1);

 getFirstRootOrder(first,middle,len,last+len-1);
 cout<<last<<endl;

 getFRONR(first,middle,last);
 cout<<last<<endl;

 delete [] first;
 delete [] middle;
 delete [] last;
}