教育网站制作下载,校园网站建设情况汇报,h5编辑工具,中视频自媒体平台注册官网原题描述#xff1a;
题目描述
时间#xff1a;1s 空间#xff1a;256M
一棵有点权的有根树如果满足以下条件#xff0c;则被轩轩称为对称二叉树#xff1a;
1. 二叉树#xff1b;
2. 将这棵树所有节点的左右子树交换#xff0c;新树和原树对应位置的结构相同且…原题描述
题目描述
时间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。 树的深度:树中节点的最大层次称为树的深度。
满二叉树设二叉树的深度为 ℎ且二叉树有 个节点这就是满二叉树。 完全二叉树设二叉树的深度为 ℎ除第 ℎ层外其它各层的结点数都达到最大个数第 ℎ 层所有的结点都连续集中在最左边这就是完全二叉树。 主要思路
很简单的一题暴力判断如果可以就ansmax(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:
#includebits/stdc.h
using namespace std;
int n,m;
int a[1000010];
int zuo[1000010],you[1000010];
int fa[1000010],zi[1000010];
int root;
//int cnt0;
bool check(int x,int y)
{if (x -1y -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])));
}
vectorint 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;cinn;for(int i1;in;i){cina[i];}for(int i1;in;i){cinzuo[i]you[i];fa[zuo[i]] i;fa[you[i]] i;if(zuo[i] -1you[i] -1){v.push_back(i);}zi[i] 1;}for(int i1;in;i){if(fa[i] 0){root i;}}
// coutzi[1]\n;
// dfs(1);for(int i1;in;i){dfs(i);}
// for(int i1;in;i)
// {
// coutzi[i] ;
// }
// cout\n;int ans0;for(int i1;in;i){if(check(zuo[i],you[i])){ans max(zi[i],ans);}}coutans;return 0;
}
