1003. 二叉树后序遍历

Total:

137

Accepted:

80

	Time Limit: 3sec    Memory Limit:256MB Description 给定一棵二叉树的前序和中序遍历顺序，输出后序遍历顺序     Input 第一行是二叉树的前序遍历顺序。二叉树的结点个数<=26，每个结点以一个大写字母表示，结点字母之间没有间隔。第二行是这棵二叉树的中序遍历顺序，表示方法和前序相同。（注：在左子树和右子树之间总是先左后右） Output 输出二叉树后序遍历的顺序 Sample Input  Copy sample input to clipboard GDAFEMHZADEFGHMZ Sample Output AEFDHZMG

通过前序遍历与中序遍历可以唯一确定二叉树

我们先重建一棵二叉树

再后序遍历

#include 
      
         #include 
       
          using namespace std;  //结点类  struct Node  {      Node * lchild;      Node * rchild;      char c;  };  //重建后续排序二叉树  Node * rebuild(string s1, string s2)  {      //建立根结点      Node * t=NULL;  //一定要初始化为NULL，不然报错      if(s1.size()>0){          t=new Node;          t->c=s1[0];          t->lchild=NULL;          t->rchild=NULL;      }      if(s1.size()>1){          //寻找根结点在中序遍历中的位置          int root;          for(int i=0; i
        
         c){                  root=i;                  break;              }          }          //左子树重建          string qianxu_left=s1.substr(1, root); //注意substr的用法，第二个参数是子字符串长度          string zhongxu_left=s2.substr(0, root);          t->lchild=rebuild(qianxu_left, zhongxu_left);          //右子树重建          string qianxu_right=s1.substr(root+1, s1.size()-root-1);          string zhongxu_right=s2.substr(root+1, s2.size()-root-1);          t->rchild=rebuild(qianxu_right, zhongxu_right);      }        return t;  }  //后序遍历：左右根  void houxu(Node * t)  {      //左子树非空，遍历左子树      if(t->lchild!=NULL)          houxu(t->lchild);      //右子树非空，遍历右子树      if(t->rchild!=NULL)          houxu(t->rchild);      //取出该结点的值      cout<
         
          c;  }    int main()  {      string s1, s2;    cin>>s1>>s2;            Node * t=rebuild(s1, s2);          houxu(t);          cout<