首页 > 代码库 > 前序遍历与中序遍历确定后序遍历

前序遍历与中序遍历确定后序遍历

1003. 二叉树后序遍历
 
 
Total: 137 Accepted: 80
 
     
     
 
Time Limit: 3sec    Memory Limit:256MB
Description

给定一棵二叉树的前序和中序遍历顺序,输出后序遍历顺序

 

 

Input

第一行是二叉树的前序遍历顺序。二叉树的结点个数<=26,每个结点以一个大写字母表示,结点字母之间没有间隔。第二行是这棵二叉树的中序遍历顺序,表示方法和前序相同。(注:在左子树和右子树之间总是先左后右)

Output

输出二叉树后序遍历的顺序

Sample Input
技术分享 Copy sample input to clipboard
GDAFEMHZ
ADEFGHMZ
Sample Output
AEFDHZMG

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

我们先重建一棵二叉树

再后序遍历

#include <iostream>  
#include <string>  
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<s2.size(); i++){  
            if(s2[i]==t->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<<t->c;  
}  
  
int main()  
{  
    string s1, s2;
    cin>>s1>>s2;
            Node * t=rebuild(s1, s2);  
        houxu(t);  
        cout<<endl;    
  
    return 0;  
}                                 

  

前序遍历与中序遍历确定后序遍历