对称二叉树(NOIP2018)_noip2018 对称二叉树

首先，我们将题目给定的对称二叉树的定义来梳理一遍：

一棵有点权的有根树如果满足以下条件
1.这是一棵二叉树
2.将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。
则这颗树就是一棵对称二叉树

我们来看9~12的数据：
这是一棵满二叉树
所以，对于这一档数据，我们只要判断他们的权值是否相等就行了

再看17~20的数据：
这是一颗所有权值都为1的二叉树
对于这一档数据，我们需要判断它的结构是否正确

对于全部的数据，我们即需要判断结构，还要判断权值，
怎么办呢

我们可以用到dfs大法！！！

接下来思路就很清晰了：
若这棵树是对称二叉树
1.他的两个子树高度相同
2.他的两个子树节点数相同
3.他的两个子树的权值和，max，min都相同

这里就可以用一个check函数来判断了

接下来附上完整代码：

#include<bits/stdc++.h>
using namespace std;
int n;
long long ans=1;
long long h,size;
long long a[1000005];
long long l[1000005];
1
2
3
4
5
6
7