M_sea

洛谷5018 对称二叉树
我怕不是心态炸了才只氵了80pt。Luogu分析暴力比较左右子树。如果左右都是-1,那就返回true。否则,比较权...
扫描右侧二维码阅读全文
22
2018/11

洛谷5018 对称二叉树

我怕不是心态炸了才只氵了80pt。

Luogu

分析

暴力比较左右子树。

如果左右都是-1,那就返回true。

否则,比较权值,然后比较左边的右子树和右边的左子树,以及比较左边的左子树和右边的右子树。

其实还可以比较一下大小和树高,这样跑的更快。

详见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=1000000+10;

int l[MAXN],r[MAXN],val[MAXN];
int sz[MAXN];
int n,ans=1;

inline void Dfs(int u) {
    sz[u]=1;
    if (l[u]!=-1) Dfs(l[u]),sz[u]+=sz[l[u]];
    if (r[u]!=-1) Dfs(r[u]),sz[u]+=sz[r[u]];
}

inline int check(int a,int b) {
    if ((a==-1)&&(b==-1)) return 1;
    else return (a!=-1)&&(b!=-1)&&sz[a]==sz[b]&&val[a]==val[b]&&check(l[a],r[b])&&check(r[a],l[b]);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) val[i]=read();
    for (re int i=1;i<=n;++i) l[i]=read(),r[i]=read();
    Dfs(1);
    for (re int i=1;i<=n;++i)
        if (check(l[i],r[i])) ans=max(ans,sz[i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2018 年 12 月 02 日 09 : 19 PM

发表评论