题目描述
知识点:1、vector容器的使用
2、递归结束条件
思路:后序遍历的最后一个数即是根节点,根据根节点找到在中序遍历的位置,区分左子树和右子树。再对左子树和右子树按先后顺序进行递归
样例
blablabla
算法1
(递归) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 35;
vector<int> level[N];
int a[N],b[N],p[N];//a表示后序遍历,b表示中序遍历,p代表b中元素所在的位置
void build(int al,int ar,int bl,int br,int d)
{
if(al>ar)
return;
int val=a[ar];
int local = p[val];
level[d].push_back(val);
build(al,local-1-bl+al,bl,local-1,d+1);
build(local-bl+al,ar-1,local+1,br,d+1);
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n;i++) p[b[i]]=i;
build(0,n-1,0,n-1,0);
for(int i=0;i<n;i++)
for(int x:level[i])
cout<<x<<" ";
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla