NOIP2018对称二叉树

题目描述

太长，直接放洛谷链接：

https://www.luogu.org/problem/P5018

题解

棉花糖还我省一！！！

这题是NOIP2018PJ第四题，考场上T3没推出来，加上食物中毒，导致T4这么一个水搜索没写完。

如果一棵树是对称的。那么对于下图的根节点，它的两个子节点(紫色)的一定要是对称的，那么对于这两个子节点，左边子节点的右儿子一定要和右边节点的左儿子对称(红色)，同理，左边子节点的左儿子一定要和右边节点的右儿子对称(橙色)。

我们只要以每个节点为根，遍历一遍它的子树，如果是对称的，则计入答案，最后取个$\max$便可。

时间复杂度：$O(n\log n)$

代码

#include <iostream>

using std::cout;
using std::cin;

/*-----------变量定义、宏定义-------------*/

#define endl '\n'
#define R register
#define max(a, b) a > b ? a : b
const int maxn = 1000006;

//v存每个节点的子节点数量
int n, ans, v[maxn];
struct node
{
    int lson, rson, data;
}z[maxn];

/*-----------子函数--------------*/

bool check(int rt1,int rt2) //判断是否对称
{
    if (rt1 == -1 and rt2 == -1) return true; //如果是单个节点，一定满足对称
    if (z[rt1].data != z[rt2].data or rt1 == -1 or rt2 == -1)
        return false; //左儿子右儿子不一样一定不满足
    int v1 = check(z[rt1].lson, z[rt2].rson);
    int v2 = check(z[rt1].rson, z[rt2].lson);
    if (!v1 or !v2) return false; //左子树右子树有一个不对称则一定不对称
    return true; //否则是对称的
}

void sum(int rt)  //预处理子节点的数量
{
    if (rt == -1) return;
    sum(z[rt].lson);
    sum(z[rt].rson);
    v[rt] += 1 + v[z[rt].lson] + v[z[rt].rson];
}

void dfs(int rt)  //每个点都试一遍
{
    if (rt == -1) return;
    if (check(z[rt].lson, z[rt].rson))
        ans = max(ans, v[rt]);
    dfs(z[rt].lson);
    dfs(z[rt].rson);
}

/*-----------主函数--------------*/

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (R int i = 1; i <= n; ++i)
        cin >> z[i].data;

    for (R int i = 1; i <= n; i++)
        cin >> z[i].lson >> z[i].rson;

    sum(1);  //预处理
    dfs(1);

    cout << ans << endl;
    return 0;
}

NOIP2018 IS END