题解 | #洛谷P1030求先序排列#

利用递归以及后序排列最后一位为根解决。

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<string>
using namespace std;
void ff(string s1,string s2)//递归函数
{
	int j=0;
	string s3,s5;
	string s4,s6;
	cout << s2[s2.size() - 1];
	if (s2.size() == 1||s1.size()==1)//一些特判
	{
		return;
	}
	if (s2.size() == 2)
	{
		cout << s2[0];
		return;
	}
	for (int i = 0; i < s1.size(); i++)
	{
		if (s1[i] == s2[s2.size() - 1])//记录根下标
		{
			j = i;
			break;
		}
		else
		{
			s3 = s3 + s1[i];
		}
	}
	for (int i = j+1; i < s1.size(); i++)
	{
		s4 += s1[i];
	}
	for (int i = 0; i < s3.size(); i++)
	{
		s5 += s2[i];
	}
	for (int i = s3.size(); i < s2.size() - 1; i++)
	{
		s6 += s2[i];
	}
	if (s3.size() == s1.size() - 1)///单子树情况
	{
		ff(s3, s5);
	}
	else if (s4.size() == s1.size() - 1)
	{
		ff(s4, s6);
	}
	else
	{
		ff(s3, s5);
		ff(s4, s6);
	}
	

}
int main()
{
	string s1;
	string s2;
	cin >> s1 >> s2;
	ff(s1, s2);

}