7-1 根据后序和中序遍历输出先序遍历（25 分）

女爷i 2022-04-22 03:26 160阅读 0赞

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

## 输入格式: ##

第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

## 输出格式: ##

在一行中输出Preorder:以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

## 输入样例: ##

7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7

## 输出样例: ##

Preorder: 4 1 3 2 6 5 7

先还原二叉树，在输出先序遍历序列。

#include <bits/stdc++.h>
    using namespace std;
    
    typedef int ElementType;
    typedef struct TNode* BTree;
    struct TNode{
        
        ElementType Data;
        BTree Left;
        BTree Right;
    };
    int n,a[101],b[101];
    void Init(){
        
        for(int i=0;i<n;i++){
        
            cin>>a[i];
        }
        for(int i=0;i<n;i++){
        
            cin>>b[i];
        }
    }
    BTree buildTree(int *a,int *b,int m){
        
        BTree t=(BTree)malloc(sizeof(TNode));
        int i;
        if(m==0)return NULL;
        for(i=0;i<m;i++){
        
            if(b[i]==a[m-1])break;
        }
        t->Left=buildTree(a,b,i);
        t->Right=buildTree(a+i,b+i+1,m-i-1);
        t->Data=a[m-1];
        return t;
    }
    BTree printTree(BTree root){
        
        if(root){
        
            cout<<" "<<root->Data;
            if(root->Left)printTree(root->Left);
            if(root->Right)printTree(root->Right);
        }
    }
    int main()
    {
        
        cin>>n;
        Init();
        BTree s=buildTree(a,b,n);
        cout<<"Preorder:";
        printTree(s);
    }