dfs,后序遍历
$O(2^n)$
先通过判断数据范围大致确定算法深搜。
看到后序遍历直接确定dfs的递归次序。
剩下的交给模板:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=55;
int l[N],r[N];
string e[N];
string dfs(int u) //后序遍历遵循:左右根
{
if(l[u]==-1&&r[u]==-1) //子节点的时候
return '('+e[u]+')';
if(l[u]==-1&&r[u]) //只有右子树时
return '('+e[u]+dfs(r[u])+')';
return '('+dfs(l[u])+dfs(r[u])+e[u]+')'; //当左右子树都存在,则按左右根顺序遍历
}
int main()
{
int n; cin>>n;
int root[N]; //存储根
memset(root,0,sizeof root); //假设都是根节点
for(int i=1;i<=n;i++)
{
cin>>e[i]>>l[i]>>r[i];
if(l[i]) root[l[i]]=1;
if(r[i]) root[r[i]]=1;
}
int x=0;
while(root[++x]);
cout<<dfs(x);
}