线上OJ:
一本通: http://ybt.ssoier.cn:8088/problem_show.php?pid=1981 (opens in a new tab)
洛谷: https://www.luogu.com.cn/problem/P5018 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/description/478/ (opens in a new tab)
这道题作为18年的第四题,确实比第三题简单许多。当前这两道题的排序真的有点坑
💡
题解代码:
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
struct Node
{
int v; // 节点的权值
int l, r; // l:左孩子节点编号 r:右孩子节点编号
int n; // 以当前节点为根的子树的节点总数(含自己)
};
Node node[N]; // node[i],存储 id 为 i 的结点
int n;
int ans; // 结点数量最大的对称子树的结点数
// 判断以 i1 为根的子树和以 i2 为根的子树是否对称
bool check(int i1, int i2)
{
if(i1 == -1 && i2 == -1) return true; // 如果两个都是空结点,则认为对称,直接返回 true
else if(node[i1].v != node[i2].v) return false; // 如果 i1 和 i2 自身的权值不相等,则不对称
else if(node[i1].n != node[i2].n) return false; // 如果以 i1 和 i2 为根的树的节点总数不等,则不对称
// 否则,判断 i1 左子树和 i2 右子树是否对称;以及 i1 右子树和 i2 左子树是否对称。只有两个都对称,才返回 true
else if( check(node[i1].l, node[i2].r) && check(node[i2].l, node[i1].r) ) return true;
else return false;
}
// 确定结点最多的对称的子树的结点数
int dfs(int i)
{
if(i != -1)
{
if(check(node[i].l, node[i].r)) // 检查左右子树是否对称
ans = max(ans, node[i].n); // 如果对称,记录最大结点数
else // 如果不对称,则对左右子树分别进行dfs
ans = max(ans, max(dfs(node[i].l), dfs(node[i].r))) ;
return ans;
}
return 0;
}
// 初始化时先计算以每个节点为根的子树的所有节点数
int init(int i)
{
if(i == -1) return 0;
else
{ // 递归计算
node[i].n = init(node[i].l) + init(node[i].r) + 1;
return node[i].n;
}
}
int main()
{
scanf("%d\n", &n);
for(int i = 1; i <= n; i++) scanf("%d", &node[i].v);
for(int i = 1; i <= n; ++i) scanf("%d %d", &node[i].l, &node[i].r);
init(1); // 从节点1开始,初始化计算树的各子树结点数
dfs(1); // 从结点1开始深搜,遍历所有子树进行判断
printf("%d", ans);
return 0;
}
备注: 虽然解法二使用了剪枝, 但从最终的运行时间来看, 提速效果并不显著。应该时测试数据所致。
理论上, 确实剪枝应该更快, 因为如果要判断的节点总数已经小于当前最大对称数的节点总数,那就不用继续dfs 了,因为即使是对称二叉树, 也不可能更新结果了。
附剪枝前和剪枝后的对比图