[NOIP2018 普及组] 对称二叉树 题解_2018noip普及组对称二叉树

题目

洛谷题目

题目背景

NOIP2018 普及组 T4

题目描述

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

2 
1 3 
2 -1 
-1 -1
1
2
3
4

样例输出 #1

1
1

样例 #2

样例输入 #2

10 
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
1
2
3
4
5
6
7
8
9
10
11
12

样例输出 #2

3
1

提示

样例 1 解释

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

样例 2 解释

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

数据规模与约定

共 $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$。

本题约定：

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

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

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

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

思路

骗分（题外话）

如果这道题没有思路的话可以尝试直接骗分，这道题非常容易骗分，对于每个点左子树和右子树的节点数、点权和等进行比较，大概能骗$44-48$分。

骗分代码（48）

#include <iostream>
using namespace std;
int n,ans=1;
struct node{
	int l=0,r=0,val=0,cnt=0,h=0,tot=0;
}m[1000009];
long long fl(int i)
{
	if(i==-1) return 1001;
	long long a=m[i].val+fl(m[i].l)*10+fl(m[i].r)*10;
	return a;
}
void cs(int i)
{
	if(m[i].l==-1&&m[i].r==-1)
	{
		m[i].tot=1;
		m[i].h=1;
		m[i].cnt=m[i].val;
		return ;
	}
	if(m[i].l!=-1) cs(m[i].l);
	if(m[i].r!=-1) cs(m[i].r);
	m[i].tot=m[m[i].l].tot+m[m[i].r].tot+1;
	m[i].h=max(m[m[i].l].h,m[m[i].r].h)+1;
	m[i].cnt=m[i].val+m[m[i].l].cnt+m[m[i].r].cnt;
	if(m[i].l!=-1&&m[i].r!=-1&&m[m[i].l].tot==m[m[i].r].tot&&m[i].tot>ans&&m[m[i].l].h==m[m[i].r].h&&m[m[i].l].cnt==m[m[i].r].cnt)
	{
		if(fl(m[i].l)==fl(m[i].r))
			ans=m[i].tot;
	}
	return ;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>m[i].val;
	for(int i=1;i<=n;i++) cin>>m[i].l>>m[i].r;
	cs(1);
	cout<<ans;
}
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

正解（正文）

由于此题数据量并不是太大，我们可以直接递归判断两个子树是否对称，再求最大值。
注意：因为判断的是对称，对于每个子节点的子树都是判断其左子树与其对应点的右子树是否对称，对于子节点为$-1$的点要进行特判，防止数组越界。

判断是否对称

bool pan(int l,int r)
{
	h++;
	if(l==-1&&r!=-1) return 0;
	if(r==-1&&l!=-1) return 0;
	if(m[l].val!=m[r].val) return 0;
	if(l==-1&&r==-1) return 1;
	return pan(m[l].l,m[r].r)&&pan(m[l].r,m[r].l);
}
1
2
3
4
5
6
7
8
9

满分代码

#include <iostream>
using namespace std;
int n,ans=1,h;
struct node{
	int l,r,val;
}m[1000009];
bool pan(int l,int r)//判断是否对称
{
	h++;//注意：求的是点数而不是层数
	if(l==-1&&r!=-1) return 0;
	if(r==-1&&l!=-1) return 0;
	if(m[l].val!=m[r].val) return 0;
	if(l==-1&&r==-1) return 1;
	return pan(m[l].l,m[r].r)&&pan(m[l].r,m[r].l);
}
void k(int x)//对每个节点进行尝试
{
	h=0;
	if(pan(m[x].l,m[x].r))
	{
		ans=max(ans,h);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>m[i].val;
	for(int i=1;i<=n;i++) cin>>m[i].l>>m[i].r;
	for(int i=1;i<=n;i++) k(i);
	cout<<ans;
}
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