搜索练习题——对称二叉树

目录

就在小蒟蒻正准备刷些\(bfs\)的题，突然来了一位大佬，开始讲一道蓝色的\(bfs\)题

---

​ 这是一道非常非常非常厉害的题目，出自一个非常非常非常牛*的比赛。是的，就是 $NOIP_{普及组} $ （应该没人看见右下角吧 \(\Omega \omega \Omega\)）

​ 对称二叉树

题目描述（自己口胡的）：

给你一个二叉树，让你找出这棵树的最大对称二叉树。什么是对称二叉树呢？？？

对称二叉树就是一棵树，以根节点向下画一条垂线，根节点的左子树和右子树关于这条垂线对称（只有权值是对称的）。两棵子树不需要是对称二叉树。

题目分析：

我们可以发现，如果存在对称二叉树，那么在一层中一定存在两个点，满足两个点一个有左儿子一个有右儿子，或者都有两个孩子。并且满足两个点的权值都是相同的。根据这个结论我们可以写出一个\(check\)函数。

​ 这就是\(wxl\)大佬给我们讲的大致思路，其他的都在代码里了

代码实现：

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

int n;
int son[1000050][2];
int val[1000050];
int size[1000050];

inline int read()//快速读入 
{
    int F=1,ans=0;
    char c;
    c=getchar();
    while(!isdigit(c)){if(c=='-') F=-1; c=getchar();}
    while(isdigit(c)){ans=ans*10+c-'0'; c=getchar();}
    return ans*F;
}

void sum_size(int u)//用来预处理size数组 
{
    size[u]=1;
    if(son[u][0]!=-1)//如果有左儿子，就进行递归求出左儿子的sum值 
    {
        sum_size(son[u][0]);
        size[u]+=size[son[u][0]];
    }
    if(son[u][1]!=-1)//如果有右儿子，就进行递归求出右儿子的sum值 
    {
        sum_size(son[u][1]);
        size[u]+=size[son[u][1]];
    }
}

inline bool check(int u,int v)
{
    if(u==-1&&v==-1)//如果这是一个叶节点，就是正确的 
        return true;
    if(u!=-1&&v!=-1&&val[u]==val[v]&&check(son[u][0],son[v][1])&&check(son[u][1],son[v][0]))//如果这两个点都满足对称二叉树的性质，就是正确的 
        return true;
    return false;
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)   val[i]=read();
    for(int i=1;i<=n;++i)
    {
        son[i][0]=read();
        son[i][1]=read();
    }
    sum_size(1);
    int ans=0;
    for(int i=1;i<=n;++i)
        if(check(son[i][0],son[i][1]))//循环求得每一个对称二叉树 
            ans=max(ans,size[i]);//每次与找到的最大值进行比较 
    printf("%d",ans);
}

好像很水诶233（我是说这篇博客