NOIP2018普及组T4（对称二叉树）题解_noip2018入门级复赛第4题

题目信息

题目传送门

解题思路

• 以二叉树的每一个节点为根节点，寻找对称二叉树。
• 统计所有对称二叉树的大小。
• 比较找出最大值。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int l[N], r[N], v[N];
int res = 1;
bool flag = true;  // 是否对称
// 函数用于寻找对称二叉树，x, y表示正在判断的两个子树中正在判断的结点，tot表示结点总数
int dfs(int x, int y, int tot) {
    if (x == -1 && y == -1) {   // 目前结点均为空
        return 0;
    }
    if ((x == -1 || y == -1 && x != y) || (v[x] != v[y])) {	// 结点不对称或权值不对称 
        flag = false;
        return 0;
    } 	
  	// 继续递归，返回值=下面节点数+上面节点数 
    return dfs(l[x], r[y], 2) + dfs(r[x], l[y], 2) + tot;
}
int main() {
    int m;
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> v[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> l[i] >> r[i];
    }
    for (int i = 1; i <= m; ++i)  {
        // 根节点和两个子节点，共3个
        int tmp = dfs(l[i], r[i], 3); 
        if (tmp > res && flag == true) {
            res = tmp;
        }
        flag = true;
    }
    cout << res << '\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