题目链接：点击打开链接
题目大意：给一个二叉树，输出中缀表达式，且加上括号表示运算的优先级。
解题思路：首先根据所有孩子结点编号寻找 1～n 中没有出现过的编号标记为 rt，即树的根结点。然后进行从 rt 结点开始 inT(rt) 如果当前 id == -1 说明当前没有结点则返回空字符串；当 r != -1 说明该结点不是叶子节点(不可能存在只有左边没有右边的情况的啦，因为那不符合一个算式～左边可以是空表示0～右边不可以的～)，那么就将左右结点的 da 和自身的 da 串成字符串，保存在自己的 da 中～如果当前 id 又不是根结点，那就在左右两边加上括号～最后输出 inT(rt) 的结果即可。
Ps：struct：如果在构造一个新的构造函数中参数里带有 string 类型，一定要补上默认的0参数构造函数；如果用 char* 替代 string，那么不需要补默认构造函数。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define ssclr(ss) ss.clear(), ss.str("") #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; struct node { int l,r,idx,local; string da; node(){} node(int l,int r,string da):l(l),r(r),da(da){} }; int rt; int vis[30]; vector<node> v; string inT(int id) { if(id==-1) return ""; if(v[id].r!=-1) { v[id].da=inT(v[id].l) + v[id].da + inT(v[id].r); if(id!=rt) v[id].da="(" + v[id].da + ")"; } return v[id].da; } int main() { int n,l,r; char da[20]; scanf("%d",&n); v.resize(30); for(int i=1;i<=n;i++) { scanf("%s%d%d",da,&l,&r); v[i]=node(l,r,da); vis[r==-1?0:r]=vis[l==-1?0:l]=1; } for(int i=1;i<=n;i++) if(vis[i]==0){rt=i; break;} cout<<inT(rt)<<endl; return 0; }
