洛谷刷题-P1030 求先序排列

    xiaoxiao2022-07-05  174

    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; }
    最新回复(0)