NOIP2018-J-4-对称二叉树的题解

原题描述：

题目描述

时间：1s   空间：256M
 

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

1. 二叉树；

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

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

 

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

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

输入格式：

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

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

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

输出格式：

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

样例1

样例输入1：

2
1 3
2 -1
-1 -1

样例输出1：

1

样例解释 1

最大的对称二叉子树为以节点 2 为树根的子树，节点数为 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

样例输出 2

3

样例解释 2

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

本题约定：

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

满二叉树：设二叉树的深度为 ℎ，且二叉树有  个节点，这就是满二叉树。

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

 主要思路：

很简单的一题，暴力判断，如果可以，就ans=max(ans,子树节点个数）

check(int l,int r)函数：

如果都是-1，那么return 1;

如果只有一个是-1，那么return 0;

如果权值不同，那么return 0;

否则：

return check(zuo[l],you[r])&&check(you[l],zuo[r]);因为都是对应的

求子树节点个数（dfs)

说了这么多，直接看代码。

请别说我说太少，是因为这题真的很简单。

代码code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000010];
int zuo[1000010],you[1000010];
int fa[1000010],zi[1000010];
int root;
//int cnt=0;
bool check(int x,int y)
{
	if (x == -1&&y == -1)
	{
		return 1;
	}
	if(x == -1||y == -1)
	{
		return 0;
	}
	if(a[x]!=a[y])
	{
		return 0;
	}
	return ((check(zuo[x],you[y])&&check(you[x],zuo[y])));
}
vector<int> v;
void dfs(int x)
{
	if(x == root)
	{
		return ;
	}
	zi[fa[x]]++;
	dfs(fa[x]);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>zuo[i]>>you[i];
		fa[zuo[i]] = i;
		fa[you[i]] = i;
		if(zuo[i] == -1&&you[i] == -1)
		{
			v.push_back(i);
		}
		zi[i] = 1;
	}
	for(int i=1;i<=n;i++)
	{
		if(fa[i] == 0)
		{
			root = i;
		}
	}
//	cout<<zi[1]<<'\n';
//	dfs(1);
	for(int i=1;i<=n;i++)
	{
		dfs(i);
	}
//	for(int i=1;i<=n;i++)
//	{
//		cout<<zi[i]<<' ';
//	}
//	cout<<'\n';
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(check(zuo[i],you[i]))
		{
			ans = max(zi[i],ans);
		}
	}
	cout<<ans;
	return 0;
}