【题解】牛牛的二叉对称树

题意

给你一棵二叉树的前序和中序序列，以及每个节点的权值，让你构建出这棵树，并且再书中找到一棵子树，子树的权值和是最大的，并且该子树是一棵对称树。对称树，指交换其所有左右子树与原树相等称为对称树。

题解

首先考虑一下一棵树如何判断其是否是对称的呢，若当前节点为，那么他的左右儿子为。要满足 ，并且递归下去其子树都满足该性质，，那么其左右子树也要满足即有，递归下去就可以判断以该节点为根的子树是否是对称了，那么如何求求大权值和的子树呢，我们可以先一遍存下以每个节点作为根的子树权值和记为。然后遍历一下每个节点即可。从上面的分析来看，我们需要存的是每个节点的左右儿子是什么，所以我们没必要用链表构建出一棵二叉树，我们在前序和中序的同时建立记录下每个节点的左右儿子即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int v[N],pre[N],in[N],L[N],R[N],vis[N];
long long sum[N];
long long dfs(int u)
{
    sum[u]=v[u];
    if(L[u]!=-1)
        sum[u]+=dfs(L[u]);
    if(R[u]!=-1)
        sum[u]+=dfs(R[u]);
    return sum[u];
}
bool judge(int l,int r)
{
    if(l==-1&&r==-1)
        return true;
    if(l!=-1&&r!=-1&&v[l]==v[r]&&judge(L[l],R[r])&&judge(R[l],L[r]))
        return true;
    return false;
}
int build(int t, int l, int r)
{
    if(l > r)
        return -1;
    int i = vis[pre[t]];
    L[pre[t]] = build(t + 1, l, i - 1);
    R[pre[t]] = build(t + 1 + i - l, i + 1, r);
    return pre[t];
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&v[i]);
    for(int i=1; i<=n; i++)
        scanf("%d",&pre[i]);
    for(int i=1; i<=n; i++)
        scanf("%d",&in[i]),vis[in[i]]=i;
    build(1,1,n);
    dfs(1);
    long long ans=0;
    for(int i=1; i<=n; i++)
    {
        if(judge(L[i],R[i]))
        {
            ans=max(sum[i],ans);
        }
    }
    printf("%lld\n",ans);
    return 0;
}