♐ CSP_J 组真题
2018年
4. 对称二叉树

线上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年的第四题,确实比第三题简单许多。当前这两道题的排序真的有点坑

💡

核心思想:

(本题可以使用 深搜dfs)
判断规则1、如果两个节点 ( i1 和 i2) 自身权值不相等, 肯定不对称
判断规则2、如果以两个节点 ( i1 和 i2) 为根 的树的 节点总数不相等, 肯定不对称
判断规则3、以上两点都满足, 则判断 i1 左子树和 i2 右子树是否对称;以及 i1 右子树和 i2 左子树是否对称。只有两个都对称,才是真的对称

注: 初始化时可以先计算 以每个节点为根的子树的所有节点数,后续可快速用于判断规则2

题解代码:

#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 了,因为即使是对称二叉树, 也不可能更新结果了。 附剪枝前和剪枝后的对比图