1119 pre- and post order traversals (30 points)

The main idea of the topic ： Given the pre order and post order, all over , To determine whether the middle order traversal is unique

Because when a node has only one child , Whether it's a left child or a right child , Their preorder traversal is the same , Post order traversal is the same .

   A                                    A

/                                           \

B                                            B

\                                           /

  C                                   C

The first order of these two trees is ABC The following sequence is CBA, So we can't be sure about the children .

We know that pre order and post order cannot uniquely determine a tree , The preamble is about the root , The last order is left and right roots , We find the first node of preorder traversal preL It must be equal to the last node of post order traversal postR,preL+1 The left child. ( When the left child does not exist , It's the right child ),postR-1 It's the right child ( Empathy ）,

If you find that preL+1 The node of is equal to postR-1 The node of , Then according to the nature of traversal , It can be either a left child or a right child , Here we can't be sure , If the title is not unique, just output one , So we regard him as both left and right . So we can find some in the preface , You can also find some in the following sequence , Then divide the left and right intervals , If you are looking for preL+1 The point of , We attribute this point to the left interval , If you find postR-1 The point of , We attribute this point to the right interval , It's easy to handle .

#include <iostream>
#include <vector>
using namespace std;
const int N = 110;
int pre[N],post[N],n,f;
vector<int>ans;
//  The first value of the preceding sequence must be equal to the last value of the following sequence ,preL+1 Is the left node  postR - 1 Is the right node 
//  When these two key When it's equal, you don't know whether it's a left node or a right node 
/*
       A       A
      /         \
     B           B
      \         /
       C       C
  The first order of these two trees is ABC The following sequence is CBA, So we can't be sure about the children 
*/
void dfs(int preL,int preR,int postL,int postR)
{   
	if(preL > preR) return ;
	if(preL == preR) 
	{
		ans.push_back(pre[preL]);
		return ;
	}
	int k = postL;
	while(pre[preL + 1] != post[k] && k <= postR) k ++;// Find the position of the next point in the previous sequence 
	if(k == postR - 1) // postR - 1 == postL + 1
      f = 1;// I'm not sure whether it's a left child or a right child 
	dfs(preL + 1,preL + k - postL + 1,postL,k);// Find the point of the left node in the post order traversal , We attribute this point to the left interval 
	ans.push_back(pre[preL]);// root 
	dfs(preL + k - postL + 2,preR,k + 1,postR - 1);
}
int main()
{
	cin >> n;
	for(int i = 0; i < n; i ++) cin >> pre[i];
	for(int i = 0; i < n; i ++) cin >> post[i];
	dfs(0,n - 1,0,n - 1);
	if(f) puts("No");
	else puts("Yes");
	for(int i = 0; i < ans.size(); i ++)
	{
		if(i != 0) cout << ' ';
		cout << ans[i];
	}
	puts("");
	return 0;
}