洛谷P5018 [NOIP2018 普及组] 对称二叉树 题解_noip对称二叉树题解

洛谷P5018 [NOIP2018 普及组] 对称二叉树 题解

题目链接：P5018 [NOIP2018 普及组] 对称二叉树

题意：

一棵有点权的有根树如果满足以下条件，则被轩轩称为对称二叉树：

1. 二叉树；
2. 将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。

下图中节点内的数字为权值，节点外的 $id$ 表示节点编号。

现在给出一棵二叉树，希望你找出它的一棵子树，该子树为对称二叉树，且节点数 最多。请输出这棵子树的节点数。

注意：只有树根的树也是对称二叉树。本题中约定，以节点 $T$ 为子树根的一棵“子 树”指的是：节点$T$ 和它的全部后代节点构成的二叉树。

【数据规模与约定】
共 $25$ 个测试点。
$v_i\le 1000$。
测试点 $1\sim 3,n\le 10$，保证根结点的左子树的所有节点都没有右孩子，根结点的右 子树的所有节点都没有左孩子。
测试点 $4\sim 8,n\le 10$。
测试点 $9\sim 12,n\le 10^5$，保证输入是一棵“满二叉树” 。
测试点 $13\sim 16,n\le 10^5$，保证输入是一棵“完全二叉树”。
测试点 $17\sim 20,n\le 10^5$，保证输入的树的点权均为 $1$。
测试点 $21\sim 25,n\le 10^6$。

对于每个点直接暴力dfs它的左右子树判断即可

注意对称的方向不要写错了

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

为什么链不会被卡呢，因为中间判断的时候已经相当于剪枝掉了

只有完全二叉树才会到 $O(n\log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e6+15)

int n,ch[N][2],val[N],sz[N];
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
void dfs(int u)
{
    sz[u]=1;
    if(ls(u)!=-1)
    {
        dfs(ls(u));
        sz[u]+=sz[ls(u)];
    }
    if(rs(u)!=-1)
    {
        dfs(rs(u));
        sz[u]+=sz[rs(u)];
    }
}
bool solve(int u,int v)
{
    if(u==-1&&v==-1)return 1;
    if(u==-1||v==-1)return 0;
    return val[u]==val[v]&&solve(ls(u),rs(v))&&solve(rs(u),ls(v));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> val[i];
    for(int i=1; i<=n; i++)
        cin >> ls(i) >> rs(i);
    dfs(1);
    int ans=0;
    for(int i=1; i<=n; i++)
        if(solve(ls(i),rs(i)))
            ans=max(ans,sz[i]);
    cout << ans << '\n';
    return 0;
}
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

转载请说明出处