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

时间:2022-01-17 12:07:00

目录

就在小蒟蒻正准备刷些\(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(我是说这篇博客