(luogu5018) 对称二叉树

发表于 分类于 ， ，

思路:

直接暴力

对于每个结点，判定其子树是否对称.

递归判定子树的对称位置是否值相等.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}