2018年信息学奥赛NOIP资料下载 题目描述 给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度 \le 8≤8）。
输入输出格式 输入格式： 22行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式： 11行，表示一棵二叉树的先序。
输入输出样例 输入样例#1： BADC BDCA 输出样例#1： ABCD
#include<bits/stdc++.h> using namespace std; struct Node{ char data; Node* left; Node* right; }; string in1,pos1; Node* build(int inl,int inr,int posl,int posr){ if(inl>inr) return NULL; Node* root=new Node; root->data=pos1[posr]; root->left=root->right=NULL; int k=0; for(int i=inl;i<=inr;i++){ if(in1[i]==pos1[posr]){ k=i;break; } } int numleft=k-inl; root->left=build(inl,k-1,posl,posl+numleft-1); root->right=build(k+1,inr,posl+numleft,posr-1); return root; } void pretra(Node* root){ if(root==NULL) return; cout<<root->data; pretra(root->left); pretra(root->right); } int main() { cin>>in1>>pos1; int n=in1.length(); Node* root=build(0,n-1,0,n-1); //cout<<root->data; pretra(root); return 0; }