PAT 1162 Postfix Expression

这一题的大意是让我们输出后缀表达式，那么很明显直接按照左右根的顺序输出即可，可是需要注意的是当左孩子不存在，右孩子存在的这一种情况，需要先输出根，再输出右孩子，而不是原来的左右根的顺序。
完整的代码如下：

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;intN;structnode{string data;intl=-1;intr=-1;intparent=-1;}n[25];stringdfs(introot){if(root==-1){return"";}string lchild="";string rchild="";if(n[root].l!=-1){lchild=dfs(n[root].l);}if(n[root].r!=-1){rchild=dfs(n[root].r);}if(lchild==""&&rchild!=""){return"("+n[root].data+rchild+")";}elsereturn"("+lchild+rchild+n[root].data+")";}intmain(){cin>>N;for(inti=1;i<=N;i++){string s;cin>>s;intl;intr;cin>>l>>r;n[i].data=s;n[i].l=l;n[i].r=r;if(l!=-1)n[l].parent=i;if(r!=-1)n[r].parent=i;}introot;for(inti=1;i<=N;i++){if(n[i].parent==-1){root=i;break;}}string ans=dfs(root);cout<<ans<<endl;return0;}

总结：本质是DFS后序遍历，但要注意特殊情况。