noip2001 求先序排列 （已知中序+後序，求解先序 ；分治）

A1132. 求先序排列

1.0s   記憶體限制：

256.0MB  

​​188​​   AC次數：

116   平均分：

68.83

将本題分享到：

​​檢視未格式化的試題​​​   

​​​送出​​​   

​​​試題讨論​​

試題來源

　　NOIP2001 普及組

問題描述

　　給出一棵二叉樹的中序與後序排列。求出它的先序排列。（約定樹結點用不同的大寫字母表示，長度<=8）。

輸入格式

　　兩行，每行一個字元串，分别表示中序和後序排列

輸出格式

　　一個字元串，表示所求先序排列

樣例輸入

BADC

BDCA

樣例輸出

ABCD

解析：用string x記錄整個二叉樹的中序排列，string y 記錄整個二叉樹的後序排列。

         write(L1，R1，L2，R2)表示輸出一個中序排列為x[L1]-x[R1]，後序排列為y[L2]-y[R2]的二叉樹的前序排列。

代碼：

#include<iostream>
#include<cstdio>
#include<string>
using namespace std; 
string x,y;

void write(int p,int q,int m,int n)
{
  if(p>q)return;
  if(p==q){cout<<x[p];return;}
  
  int i,j,k;
  k=x.find(y[n]);
  cout<<y[n];
  write(p,k-1,m,m+k-p-1);
  write(k+1,q,m+k-p,n-1);
}
int main()
{
  int i,j,k;
  cin>>x>>y;
  k=x.length();
  write(0,k-1,0,k-1);
  return 0;
}