树的遍历顺序有关

前序，中序，后序概念自行百度。

知道几种顺序来确定二叉树形态

首先先明确一点至少要知道两种顺序以上才能确定一个树，因为如果只知道前序或者后序就只能确定根节点，而不能确定根节点的左右子树。但如果知道中序，那就不能确定根节点。

然后如果知道两种顺序的话，必须要知道中序，因为另外一种顺序可以确定根节点，中序来确定根节点的左右子树，然后再根据前序后者后序确定根节点的左右儿子。

具体确定代码实现（前序+中序）

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+50;
string s,t;
int n;
void solve(int l,int r,int ml,int mr)
{
	if(l>r)
		return;
	if(l==r)
	{
		cout<<s[l];
		return;
	}
	int pos;
	for(int i=ml;i<=mr;i++)
		if(t[i]==s[l])
			pos=i;
	solve(l+1,l-ml+pos,ml,pos-1);solve(l-ml+pos+1,r,pos+1,r);
	cout<<s[l];
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>s>>t;
	n=s.length();
	s=" "+s;t=" "+t;
	solve(1,n,1,n);
	return 0;
}

结合代码还是很好理解的。

但还有一种题型，就是已知前序和后序，求有多少种二叉树满足这种遍历顺序。

我们能确定根节点，但是不能确定根节点有一个儿子还是两个儿子。如果一个点有一个儿子，那么就有两种情况，儿子朝左朝右都可以。比如看前序遍历的第二个数，再在后序中找到，如果在后序的下一个位置为根，那么证明根节点只有一个儿子。否则就有两个儿子。

具体代码实现如下。

#include<bits/stdc++.h>
using namespace std;
const int N=5050;
long long ans;
int n,m;
char a[N],b[N];
int main(){
	scanf("%s %s",a,b);
	n=strlen(a);
	for(int i=0;i<n-1;i++)
		for(int j=1;j<n;j++)
			if(a[i]==b[j]&&a[i+1]==b[j-1])ans++;
	printf("%lld\n",(1ll<<ans));
	return 0;
}

多叉树转二叉树

记住口诀** “左儿子，右兄弟” **。

\(Code\)：

#include<bits/stdc++.h>
using namespace std;
const int N=150;
map<char,char> son,L,R;
map<char,bool> mp,F,xx;
bool hav[N];
char root;int n;
void pre(char u)
{
	cout<<u;
	if(hav[u])pre(L[u]);
	if(mp[u])pre(R[u]);
	return;
}
void mid(char u)
{
	if(hav[u])mid(L[u]);
	cout<<u;
	if(mp[u])mid(R[u]);
	return;
}
void su(char u)
{
	if(hav[u])su(L[u]);
	if(mp[u])su(R[u]);
	cout<<u;
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char u;cin>>u;xx[u]=true;
		char x;
		while(1)
		{
			cin>>x;
			if(x=='0')break;
			F[x]=true;
			if(!hav[u])L[u]=x;
			else R[son[u]]=x,mp[son[u]]=true;
			son[u]=x;hav[u]=true;
		}
	}
	for(char i='A';i<='Z';i++)
	{
		if(xx[i]&&!F[i])
		 	root=i;
	}
	pre(root);cout<<endl;mid(root);cout<<endl;su(root);
	return 0;
}