社区讨论

递归写寄了 可是思路应该没问题qwq

CCLCK
P5018[NOIP 2018 普及组] 对称二叉树参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo7kws2k
此快照首次捕获于
2023/10/27 03:30
2 年前
此快照最后确认于
2023/10/27 03:30
2 年前
查看原帖
如题，应该是递归爆栈导致了MLE \kk
思路：从1开始枚举树的起点，开始枚举以该点为根的子树，之后判断根的左右子树是否存在&权值是否相同，如果相同则继续判断左子树的左子树和右子树的右子树是否相同和左子树的右子树和右子树的左子树（晕了，反正就是空间对称的递归），最后到叶节点时返回结束递归。
封装了3个用来解题的函数，但是MLE，求大佬帮忙看看哪里不大对（）
CPP
#include <iostream>
#include <algorithm>
using namespace std;
struct point {
    int l, r;
    int val;
} p[1000005];
int n, ans = -1;
void add(int t, int l, int r) {
    p[t].l = l;
    p[t].r = r;
}
bool checksm(int l, int r) {
    if (p[p[l].l].val == p[p[r].r].val && p[p[r].l].val == p[p[l].r].val) {
        if (p[l].l == -1) return checksm(p[l].r, p[r].l);
        if (p[l].r == -1) return checksm(p[l].l, p[r].r);
    if (p[l].l != -1 && p[l].r != -1)
        return checksm(p[l].r, p[r].l) && checksm(p[l].l, p[r].r);
    if (p[l].l == -1 && p[l].r == -1)
        return true;
    } else return false;
}
bool check(int rt) {
    if (p[p[rt].l].val != p[p[rt].r].val) return false;
    if (p[rt].l == -1 && p[rt].r == -1) return true;
    if (p[rt].l == -1 || p[rt].r == -1) return false;
    return checksm(p[rt].l, p[rt].r);
}
int count(int rt) {
    if (p[rt].l != -1 && p[rt].r != -1) return count(p[rt].l) + count(p[rt].r) + 1;
    else if (p[rt].l != -1) return count(p[rt].l) + 1;
    else if (p[rt].r != -1) return count(p[rt].r) + 1;
    else return 1;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int v;
        cin >> v;
        p[i].val = v;
    }
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        add(i, l, r);
    }
    for (int i = 1; i <= n; i++) {
        if (check(i)) {
            ans = max(ans, count(i));
        }
    }
    cout << ans << endl;
    return 0;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...