洛谷 P5018 [NOIP2018 普及组] 对称二叉树 题解

传送门：[NOIP2018 普及组] 对称二叉树 - 洛谷

老样子，先建树

#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
	long long l,r,val;
}bt[1000002];//val表示点权，l表示左子树索引，r表示右子树索引
int main()
{
    cin>>n;
	for(int i=1;i<=n;i++)cin>>bt[i].val;
	for(int i=1;i<=n;i++)cin>>bt[i].l>>bt[i].r;//按题目要求输入
	return 0；
}

一.大致思路

题目要求我们求给定的树的最大对称二叉子树的节点数，那么我们就以$[1,n]$为子树的根节点，DFS该子树是否为对称二叉树，再进行节点的计数

二.分解

1.检查是否为对称二叉树

搜索的DFS函数为bool函数，返回值为true则为对称二叉树，false就不是。我们就从该子树的根节点开始搜索，以$lnow$与$rnow$为向其左右子树搜索的节点编号，那么就分为两部分检查：

1.结构

2.权值

检查结构时，要么全是-1(空)，要么全是编号(都有子树)，否则就是结构不完整，直接返回false，当然如果全是-1，就不能再搜了(边界)，返回true。

权值不必多说，不相等就返回false。

如果没问题就进行进一步的搜索，注意：如果当$lnow$向左搜时，$rnow$向右搜，当$lnow$向右搜时，$rnow$向左搜以满足其对称性！

如果上述两种搜索方式返回true，则该树为对称二叉树，返回true。

bool same(long long lnow,long long rnow)
{
	if(lnow==-1&&rnow==-1)return true;
	if(lnow==-1||rnow==-1)return false;//结构检查
	if(bt[lnow].val!=bt[rnow].val) return false;//权值检查
	return same(bt[lnow].l,bt[rnow].r)&&same(bt[lnow].r,bt[rnow].l);//向下搜索
}

2.节点计数

该函数为int类型，返回节点数，对于一个节点$pos$，其节点及其子树的节点和为其本身的一个节点，以及其左、右子树的节点数，递归边界为$pos!=-1$(不为子节点)

int count(long long pos)
{
    if(pos==-1)return 0;
    else return count(bt[pos].l)+count(bt[pos].r)+1;
}

三.总代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;//ans记录答案
struct node
{
	long long l,r,val;
}bt[1000002];
bool same(long long lnow,long long rnow)
{
	if(lnow==-1&&rnow==-1)return true;
	if(lnow==-1||rnow==-1)return false;
	if(bt[lnow].val!=bt[rnow].val) return false;
	return same(bt[lnow].l,bt[rnow].r)&&same(bt[lnow].r,bt[rnow].l);
}
int count(long long pos)
{
    if(pos==-1)return 0;
    else return count(bt[pos].l)+count(bt[pos].r)+1;
}
int main()
{
    cin>>n;
	for(int i=1;i<=n;i++)cin>>bt[i].val;
	for(int i=1;i<=n;i++)cin>>bt[i].l>>bt[i].r;
    for(int i=1;i<=n;i++)if(same(i,i))ans=max(ans,count(i));
    cout<<ans;
	return 0;
}

 AC!