二叉树与递归总是有着千丝万缕的关系
由遍历的定义：
前序遍历： 根左右
中序遍历： 左根右
后序遍历： 左右根
知前、中可以推出后
知中、后可以推出前
知前、后推不出中（但肯定有一些有趣的性质）
例题思路：
递归的思想，从前（后）序遍历中得到根节点（若前序遍历则根在首位，若后序遍历则根在末尾），再在中序遍历中找到根节点的位置，从而把两个序列都分为两个子树，再对每个子树操作一遍，从而递归实现。从这个思路来看，没有中序遍历是不行的。
看代码就懂了
#include<bits/stdc++.h>
using namespace std;
void solve(string pre,string inor){//pre为前序，inor为中序
if(!pre.empty())
{
char root=pre.front();pre.erase(pre.begin());//得到根节点
int k=inor.find(root);///在中序遍历中找到根的位置
solve(pre.substr(0,k),inor.substr(0,k));//递归左子树
solve(pre.substr(k),inor.substr(k+1));//递归右子树
cout<<root;//求后序遍历所以最后输出根，若求前序就放在最前面
}
}
int main()
{
string pre,inor;
cin>>inor>>pre;
solve(pre,inor);
return 0;
}下面思考刚才那个问题，具有相同的前序遍历和后续遍历的树有什么有趣的性质呢？
可供思考的小例子：
已知前序遍历为123，后序遍历为321，求中序遍历
考虑两个树
这两棵树显然都满足条件，但他们的中序遍历却不相同,所以知道前、后无法推出中。有没有注意到他们都像一条链一样，透露一个小细节，满足题目条件的树有四种。
看了例子，有没有产生一个想法：无法判断当且仅当只有一个子树，想到这就基本正确了
来试试这个题
洛谷P1129 已知前序遍历和中序遍历，求满足情况的树的个数
相同的思路，找到子树的根，再递归处理
可子树的根不太好找，因为如果只有一个子树的话，你无法确定它是左子树还是右子树。去掉整个树的根后，若前序的头与后序的尾不相同，则说明有两棵子树，再像上题那样分割后，递归操作就解决了。若相同，则说明只有一棵子树，那么情况数乘2，继续递归处理（把它看作左或右子树都行，没区别）
上代码
#include<bits/stdc++.h>
using namespace std;
int ans=1;
void solve(string pre,string pos){
if(!pre.empty())
{
pre.erase(0,1);pos.erase(pos.size()-1,1);//去掉根
if(pre.empty())return;
char root1=pre.front();//左子树的根
char root2=pos.back();//右子树的根
if(root1==root2)//相等说明只有一个子树
{
ans*=2;//可以是左也可以是右，所以答案乘2
solve(pre,pos);//递归解决
}
else//有两棵子树
{
int k1=pre.find(root2);//找到先序中右根的位置
int k2=pos.find(root1);//找到后序中左根的位置
if(k1!=k2+1)//左子树个数不一致，说明数据无法构成数，输出0
{
cout<<0;
exit(0);
}
solve(pre.substr(0,k1),pos.substr(0,k2+1));//递归解决
solve(pre.substr(k1),pos.substr(k2+1));
}
}
}
int main()
{
string pre,pos;
cin>>pre>>pos;
solve(pre,pos);
cout<<ans;
return 0;
}
京公网安备 11010502036488号