算法思想

所谓对称二叉树满足两个条件：
1. 二叉树； 
2. 将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。

重点看第2条， 将这棵二叉树所有节点的左右子树交换，即每个节点的右子树（如果存在的话）变为左子树、左子树（如果存在的话）变为右子树，交换之后点权相等且对应位置的结构相同。

那么，一棵以T为根的二叉树是对称二叉树需满足以下性质：

• 如果T的左右子树都为空，那么T是一棵对称二叉树。只有树根的树也是对称二叉树。

• 如果T的左右子树不为空，不妨设左右子树的根节点为u和v，那么T是一棵对称二叉树，需要满足：

  • u和v的点权相同
  • 子树u的大小（树中节点的个数）和v一样，保证结构相同的必要条件。
  • u的左子树和v的右子树满足上述对称二叉树的性质，因为交换之后u的左子树成为v的右子树。
  • u的右子树和v的左子树满足上述对称二叉树的性质，因为交换之后u的右子树成为v的左子树。

算法步骤

分析出上述性质，就可以通过树的深度优先遍历计算出树中最大对称二叉子树的节点数。
1. 计算出树中以每个节点为根的子树大小（子树中节点的个数）si[i]
2. 从根节点u开始深度优先遍历，计算树中最大对称二叉树的节点个数：
①如果u满足对称二叉树的性质，那么ans = si[u]
②如果u 不满足对称二叉树的性质，那么到左右子树搜索最大对称二叉树。

时间复杂度

所有节点都需要遍历一次，所以时间复杂度为$O(n)$

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1000010;

int n, w[N], l[N], r[N], si[N];

int getSize(int u)
{
    if(!u) return 0;
    if(si[u]) return si[u];
    si[u] = 1 + getSize(l[u]) + getSize(r[u]);
    return si[u];
}

bool check(int u, int v)
{
    if(u == 0 && v == 0) return true; //两个空结点
    else if(w[u] != w[v]) return false; //权值不相等
    else if(si[u] != si[v]) return false; //树的大小不同
    //u树左子树和v右子树相同 并且u树右子树和v左子树相同
    else return check(l[u], r[v]) && check(r[u], l[v]); 
}

int dfs(int u)
{
    if(!u) return 0; //u树为空
    int ans = 0;   

    //u树的左右子树对称
    if(check(l[u], r[u])) ans = si[u];
    else ans = max(dfs(l[u]), dfs(r[u]));

    return ans;
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);

    for(int i = 1; i <= n; i ++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        //为了方便处理数组下表，如果左右儿子为空，则为0
        if(u != -1) l[i] = u; 
        if(v != -1) r[i] = v;
    }

    //递归算出树中以每个节点为根的子树大小
    getSize(1);

    cout << dfs(1) << endl;

    return 0;
}