[NOIP 2018 普及组] 对称二叉树

GitHub 跳转原题关系图返回列表

后序计算每棵子树的正常表示和镜像表示，若二者相等则该子树对称，再用子树大小更新最大答案。

OJ: luogu

题目 ID: P5018

难度:普及+/提高

标签:二叉树树形结构思维

日期: 2026-06-19 21:24

题意

给出一棵有点权的二叉树，要求找出其中节点数最多的一棵对称子树。

这里“对称”指的是：把整棵子树的左右儿子全部交换后，结构仍然对应，且对应节点权值也相等。

思路

最直接的办法是枚举每个节点，暴力比较它的左子树和右子树是否镜像相同。

先看一个可以直接验证想法的朴素解：

cpp

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 <bits/stdc++.h>
using namespace std;

static vector<int> value_arr;
static vector<int> left_son;
static vector<int> right_son;
static vector<int> subtree_size;

int calc_size(int u) {
    if (u == -1) {
        return 0;
    }
    subtree_size[u] = calc_size(left_son[u]) + calc_size(right_son[u]) + 1;
    return subtree_size[u];
}

bool mirror_same(int a, int b) {
    if (a == -1 && b == -1) {
        return true;
    }
    if (a == -1 || b == -1) {
        return false;
    }
    if (value_arr[a] != value_arr[b]) {
        return false;
    }
    return mirror_same(left_son[a], right_son[b]) &&
           mirror_same(right_son[a], left_son[b]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    value_arr.assign(n + 1, 0);
    left_son.assign(n + 1, -1);
    right_son.assign(n + 1, -1);
    subtree_size.assign(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        cin >> value_arr[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> left_son[i] >> right_son[i];
    }

    calc_size(1);

    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (mirror_same(left_son[i], right_son[i])) {
            ans = max(ans, subtree_size[i]);
        }
    }
    cout << ans << '\n';
    return 0;
}

brute.cpp 用 mirror_same(a, b) 直接递归比较左右两棵子树是否镜像一致，逻辑很直观。但这样会重复比较很多相同子结构，面对 10^6 规模不够稳。

镜像关系

这张图展示对称判断时要比较的对应关系：

graph TD
  A["u"] --> B["左子树"]
  A --> C["右子树"]
  B -.镜像对应.-> C

判断一棵子树是否对称，本质上是在问：左子树和右子树在镜像意义下是否完全一致。如果每次都真的深入比较整棵子树，会做很多重复工作。

更好的办法是先为每棵子树准备两种摘要：

正常表示：按“左、右”顺序描述这棵子树
镜像表示：按“右、左”顺序描述这棵子树

于是：

如果 normal[u] == mirror[u]，说明以 u 为根的整棵子树对称

所以正式解做一次后序遍历即可：

先处理左右儿子
组合得到当前节点的正常表示和镜像表示
若两种表示相同，则这棵子树对称
用子树大小更新答案

代码里使用双哈希保存这两种表示，并用迭代后序遍历避免深递归爆栈。

代码

cpp

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

struct HashValue {
    ull a;
    ull b;
};

struct Frame {
    int u;
    int state;
};

static const ull NULL_A = 1469598103934665603ULL;
static const ull NULL_B = 1099511628211ULL;

ull splitmix64(ull x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

HashValue combine_hash(int value, const HashValue &left_hash,
                       const HashValue &right_hash) {
    ull x = splitmix64((ull)(value + 1007) ^
                       (left_hash.a * 0x9e3779b97f4a7c15ULL) ^
                       (right_hash.a * 0xc2b2ae3d27d4eb4fULL));
    ull y = splitmix64((ull)(value + 2003) ^
                       (left_hash.b * 0x94d049bb133111ebULL) ^
                       (right_hash.b * 0xbf58476d1ce4e5b9ULL));
    return {x, y};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> value(n + 1);
    vector<int> left_son(n + 1), right_son(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> value[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> left_son[i] >> right_son[i];
    }

    vector<int> subtree_size(n + 1, 0);
    vector<HashValue> normal_hash(n + 1, {0, 0});
    vector<HashValue> mirror_hash(n + 1, {0, 0});
    vector<int> order;
    order.reserve(n);

    vector<Frame> st;
    st.reserve(n * 2);
    st.push_back({1, 0});

    while (!st.empty()) {
        Frame cur = st.back();
        st.pop_back();

        int u = cur.u;
        if (u == -1) {
            continue;
        }

        if (cur.state == 0) {
            st.push_back({u, 1});
            st.push_back({right_son[u], 0});
            st.push_back({left_son[u], 0});
        } else {
            order.push_back(u);
        }
    }

    int ans = 1;
    for (int u : order) {
        HashValue left_norm = (left_son[u] == -1 ? HashValue{NULL_A, NULL_B}
                                                 : normal_hash[left_son[u]]);
        HashValue right_norm = (right_son[u] == -1 ? HashValue{NULL_A, NULL_B}
                                                   : normal_hash[right_son[u]]);
        HashValue left_mirror =
            (left_son[u] == -1 ? HashValue{NULL_A, NULL_B}
                               : mirror_hash[left_son[u]]);
        HashValue right_mirror =
            (right_son[u] == -1 ? HashValue{NULL_A, NULL_B}
                                : mirror_hash[right_son[u]]);

        int left_size = (left_son[u] == -1 ? 0 : subtree_size[left_son[u]]);
        int right_size = (right_son[u] == -1 ? 0 : subtree_size[right_son[u]]);
        subtree_size[u] = left_size + right_size + 1;

        normal_hash[u] = combine_hash(value[u], left_norm, right_norm);
        mirror_hash[u] = combine_hash(value[u], right_mirror, left_mirror);

        if (normal_hash[u].a == mirror_hash[u].a &&
            normal_hash[u].b == mirror_hash[u].b) {
            ans = max(ans, subtree_size[u]);
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

每个节点只在后序过程中被处理常数次，所以总时间复杂度是 $O(n)$ ，空间复杂度也是 $O(n)$ 。

总结

这题的核心不是“如何一棵棵比较子树”，而是“如何给子树做摘要表示”。一旦能快速判断“原树摘要”和“镜像摘要”是否一致，最大对称子树就能在线性时间内找出来。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P5018 [NOIP 2018 普及组] 对称二叉树

题目背景

NOIP2018 普及组 T4

题目描述

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

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

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

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

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

输入格式

第一行一个正整数 $n$ ，表示给定的树的节点的数目，规定节点编号 $1 \sim n$ ，其中节点 $1$ 是树根。

第二行 $n$ 个正整数，用一个空格分隔，第 $i$ 个正整数 $v_i$ 代表节点 $i$ 的权值。

接下来 $n$ 行，每行两个正整数 $l_i, r_i$ ，分别表示节点 $i$ 的左右孩子的编号。如果不存在左 / 右孩子，则以 $-1$ 表示。两个数之间用一个空格隔开。

输出格式

输出文件共一行，包含一个整数，表示给定的树的最大对称二叉子树的节点数。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
8
9
10
11
1210 
2 2 5 5 5 5 4 4 2 3 
9 10 
-1 -1 
-1 -1 
-1 -1 
-1 -1 
-1 2 
3 4 
5 6 
-1 -1 
7 8

输出 #2

text

说明/提示

样例 1 解释

最大的对称二叉子树为以节点 $2$ 为树根的子树，节点数为 $1$ 。

样例 2 解释

最大的对称二叉子树为以节点 $7$ 为树根的子树，节点数为 $3$ 。

数据规模与约定

共 $25$ 个测试点。

$v_i ≤ 1000$ 。

测试点 $1 \sim 3, n ≤ 10$ ，保证根结点的左子树的所有节点都没有右孩子，根结点的右子树的所有节点都没有左孩子。
测试点 $4 \sim 8, n ≤ 10$ 。
测试点 $9 \sim 12, n ≤ 10^5$ ，保证输入是一棵“满二叉树” 。
测试点 $13 \sim 16, n ≤ 10^5$ ，保证输入是一棵“完全二叉树”。
测试点 $17 \sim 20, n ≤ 10^5$ ，保证输入的树的点权均为 $1$ 。
测试点 $21 \sim 25, n ≤ 10^6$ 。

本题约定：

层次：节点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一节点的层次等于其父亲节点的层次加 $1$ 。

树的深度：树中节点的最大层次称为树的深度。

满二叉树：设二叉树的深度为 $h$ ，且二叉树有 $2^h-1$ 个节点，这就是满二叉树。

完全二叉树：设二叉树的深度为 $h$ ，除第 $h$ 层外，其它各层的结点数都达到最大个数，第 $h$ 层所有的结点都连续集中在最左边，这就是完全二叉树。

[NOIP 2018 普及组] 对称二叉树

目录

题意

思路

镜像关系

代码

复杂度

总结

一图流解析