(luogu5018)对称二叉树 发表于 2019-10-24 | 分类于 solution , 搜索 , dfs 思路:直接暴力 对于每个结点, 判定其子树是否对称. 递归判定子树的对称位置是否值相等. 代码:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <cstdio>#include <cctype>const int Mn(1000500);void qrd(int& x) //快读{ x=0; int o(1); char c(getchar()); while(!isdigit(c)) { if(c=='-') o = -1; c=getchar(); } while(isdigit(c)) { x = (x<<3) + (x<<1); x += c-'0'; c=getchar(); } x *= o;}int chd[Mn][2],sz[Mn],val[Mn]; //左右儿子, 子树结点数, 结点值void count_size(int p) //计算子树结点数{ if(p==-1) return; sz[p] = 1; count_size(chd[p][0]); count_size(chd[p][1]); sz[p] += sz[chd[p][0]] + sz[chd[p][1]];}bool is_sym(int u,int v) //判定对称{ if(u==-1 && v==-1) return true; //如果对称位置均为空 else if((u!=-1&&v!=-1) && val[u]==val[v] && is_sym(chd[u][0],chd[v][1]) && is_sym(chd[u][1],chd[v][0])) /*如果对称位置均不为空且值相等*/ return true; else return false;}int main(){ int n; qrd(n); for(int i(1);i<=n;++i) qrd(val[i]); for(int i(1);i<=n;++i) { qrd(chd[i][0]); qrd(chd[i][1]); } count_size(1); int mxsz(0); //储存答案 for(int i(1);i<=n;++i) { if(is_sym(chd[i][0],chd[i][1])) //判定对称位置, 从左右儿子开始 if(mxsz<sz[i]) mxsz = sz[i]; //更新答案 } printf("%d",mxsz); return 0;}