树形结构

对称二叉树

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

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

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

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

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

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

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

接下来 nnn 行，每行两个正整数 li,ril_i, r_ili​,ri​，分别表示节点 iii 的左右孩子的编号。如果不存在左 / 右孩子，则以 −1-1−1 表示。两个数之间用一个空格隔开。
输出格式

输出文件共一行，包含一个整数，表示给定的树的最大对称二叉子树的节点数。
样例：输入：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
输出：3

解题思想：从根节点开始遍历，判断从每个节点开始到其树的底部是否为堆成二叉树（利用镜面对称的思想）；
先弄清概念，何为对称二叉树，并非是指一棵树的对称的那一部分便是对称二叉树。
如图所示，所谓的对称二叉树既不是黄色笔和黑色笔所圈的子数，而是蓝色笔所圈才为其解，如图可知最大二叉树的节点总数为3.
但得区分另一张图：如下：黄色笔和红色笔所圈的此时都不是对称的，黄色是因为其其底部还有别的节点，红色则是因为不对称，，（这下应该清楚概念了吧）
而镜面对称利用递归的思想便可求解。
代码如下：
#include
#include<math.h>
using namespace std;
int n;
int v[1000001]={0};
int l[1000001]={0};
int r[1000001]={0};
//镜面对称
int ans=1;
bool q;
int sum=1;
void check(int a,int b)
{
if(a==-1&&b==-1)return;
if(a==-1||b==-1||v[a]!=v[b])
{
q=false;
return;
}
check(l[a],r[b]);
check(r[a],l[b]);
}
void num(int x)
{
if(l[x]!=-1)sum++,num(l[x]);
if(r[x]!=-1)sum++,num(r[x]);
}

int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=n;i++)
cin>>l[i]>>r[i];
for(int i=1;i<=n;i++)
{
if(l[i]!=-1&&r[i]!=-1&&v[l[i]]==v[r[i]])//必须满足该条件才可能有对称二叉树
{

		q=true;
		check(l[i],r[i]);
		if(q)
		{
		num(i);
		ans=max(ans,sum);
		sum=1;
		}
	}
}
cout<<ans;
1
2
3
4
5
6
7
8
9
10
11

}

如有不对的地方，请指出，好改进，谢谢。
如有不懂的地方，请在评论下方提出，本博主看到会（随当时的心情）解答。。没错，就是这么任性