APP和网站是一样吗,郑州网站建设公司,网站和后台建设,百度seo怎么做网站内容优化题目
P5018 对称二叉树 https://www.luogu.com.cn/problem/P5018
代码
思路#xff1a;领接表存储二叉树#xff0c;unordered_map存储各个节点对应的值。dfs遍历一下各个子树的大小个数#xff0c;再写个递归判断是否是对称二叉树#xff0c;如果是就更新全局答案。
#…题目
P5018 对称二叉树 https://www.luogu.com.cn/problem/P5018
代码
思路领接表存储二叉树unordered_map存储各个节点对应的值。dfs遍历一下各个子树的大小个数再写个递归判断是否是对称二叉树如果是就更新全局答案。
#include bits/stdc.h
#define endl \nusing namespace std;const int N 1e7 10;// 对于每个点k开一个单链表存储k所有可以走到的点。h[k]存储这个单链表的头结点也就是邻接表
int e[N], ne[N], h[N], st1[N], idx;unordered_mapint, int mp;// 每个结点id对应的值
int max_n 0; // 最大对称二叉树节点数量// 邻接表初始化
void init() {memset(h, -1, sizeof h);idx 0;
}// 添加一条边a-b
void add(int a, int b) {// 存下b的值b下一个指向a的下一个节点a的下一个节点指向be[idx] b, ne[idx] h[a], h[a] idx ;
}//p, q是指针
bool check(int p, int q) {if (mp[e[p]] 0 mp[e[q]] 0) // 递归到结尾返回truereturn true;else if (mp[e[p]] 0 || mp[e[q]] 0) // 两个孩子有一个为空返回falsereturn false;else if (mp[e[p]] ! mp[e[q]]) // 左孩子和右孩子不相同返回falsereturn false;return check(h[e[p]], ne[h[e[q]]]) check(ne[h[e[p]]], h[e[q]]); // 左右两颗子树开始递归
}int dfs(int u) {if (mp[u] 0) // 没有节点返回0return 0;st1[u] true;// st[u] 表示点u已经被遍历过int sum 0;for (int i h[u]; i ! -1 ; i ne[i]) {int j e[i];if (st1[j]) continue;// 防止逆向dfsint s dfs(j);sum s; // 累加左孩子右孩子节点数}// 检查是不是对称二叉树并更新答案if (check(h[u], ne[h[u]])) {max_n max(max_n, sum 1);}return sum 1; // 返回当前节点的左孩子右孩子所有结点数1
}int main() {cin.tie(0), cout.tie(0);init();mp[-1] 0;int n;cin n;// 每个节点存下节点值for (int i 1; i n; i ) {int v;cin v;mp[i] v;}// 插入左孩子右孩子for (int i 1; i n; i ) {int l, r;cin l r;add(i, r);add(i, l);}// 从1开始dfsdfs(1);cout max_n endl;return 0;
}
