首页 > 其他 > 详细

【Noip2018pj】【对称二叉树】

时间:2019-02-10 23:45:38      阅读:388      评论:0      收藏:0      [点我收藏+]

纪念一下这题考场\(AC\),从而稳住了省一\(qaq\).其实个人认为这题没有\(T3\)难,,只要稍微模拟一下就好了。

正文部分

首先我们可以画一颗二叉树
技术分享图片
图片来自于互联网。至于点权不用在意。
然后我们就找到了一种模拟方法:
对于一个节点,有两种往下递推方法:
①:左边节点向左边走,右边节点往右边走
②:左边节点往右边走,右边节点往左边走。
至于为什么是对的?其实自己在这张图上模拟一下就好了。
有了基本的思想,我们就可以开始构造函数。
对于check(int,int)函数,表示当前递归到的LR。看一下这部分的代码:

    if(now_l == -1 && now_r == -1) return 1;    
    //没有节点,返回正确
    if(val[now_l] != val[now_r]) return 0;
    //权值不等,返回错误
    if(!in_chk(now_l,now_r)) return 0;   
    //结构不等,返回错误
    int i;
    if(!check(tree[now_l][0] , tree[now_r][1]))
    //递归情况1不满足,返回错误
    return 0;
    if(!check(tree[now_l][1] , tree[now_r][0]))
    //递归情况2不满足,返回错误
    return 0;
    //两种情况都满足,返回正确。
    return 1; 

对于in_chk函数,无非就是特判一下-1的情况,可以自行理解。
对于memson函数,预处理出所节点的子节点数,注意返回时要+1,因为还要算上自身。
最后附上考场代码

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define il inline
#define gc getchar
const int MAXN = 1e6 + 10;
const int INF = 0x7f7f7f7f;
using namespace std;
int sons[MAXN],tree[MAXN][2],val[MAXN];
int n,m,i,j,k,Ans = -INF;
il int read() {
    int ret = 0;char c;bool sign = 0;
    for(c = gc();!isdigit(c);c = gc()) sign |= c == ‘-‘;
    for(;isdigit(c);c = gc()) ret = (ret << 1) + (ret << 3) + (c ^ 48);
    return sign ? -ret : ret;
}
int memson(int now) {
    int ret = 0;
    if(tree[now][0] != -1) ret += memson(tree[now][0]);
    if(tree[now][1] != -1) ret += memson(tree[now][1]);
    return sons[now] = ret + 1;
}
il bool in_chk(int a,int b) {
    if(tree[a][0] == -1 && tree[b][1] != -1) return 0;
    if(tree[a][1] == -1 && tree[b][0] != -1) return 0;
    if(tree[b][0] == -1 && tree[a][1] != -1) return 0;
    if(tree[b][1] == -1 && tree[a][0] != -1) return 0;
    return 1;
}
bool check(int now_l , int now_r) {
    if(now_l == -1 && now_r == -1) return 1;  
    if(val[now_l] != val[now_r]) return 0;
    if(!in_chk(now_l,now_r)) return 0;
    int i;
    if(!check(tree[now_l][0] , tree[now_r][1])) return 0;
    if(!check(tree[now_l][1] , tree[now_r][0])) return 0;
    return 1; 
}
int main() {
    n = read();
    for(i = 1;i <= n;i++) val[i] = read();
    for(i = 1;i <= n;i++) tree[i][0] = read(),tree[i][1] = read();
    memson(1);  
    for(i = 1;i <= n;i++) {
        if(tree[i][0] == -1 && tree[i][1] == -1) Ans = max(Ans,1);
        else {
            if(val[tree[i][0]] != val[tree[i][1]]) continue;
            if(tree[i][0] == -1 && tree[i][1] != -1) continue;
            if(tree[i][1] == -1 && tree[i][0] != -1) continue;
            if(check(tree[i][0],tree[i][1])) Ans = max(Ans,sons[i]);    
        } 
    }
    printf("%lld",1LL * Ans);
    return 0;
}

【Noip2018pj】【对称二叉树】

原文:https://www.cnblogs.com/Sai0511/p/10360598.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!