题解：对称二叉树

思路

因为这道题只要求最大的节点数量，所以我们只用枚举“根节点”的位置，然后判断是否对称，如果对称，统计这棵子树的节点数并记录 ans 。
cnt 与 main 函数过于简单故不在此处展开赘述，单独看看 same 函数——判断是否对称。我们一次需要两个位置来判断对称，而这两棵子树对称，当且仅当它们的儿子们全部对称，便可以从此处向下递归。递归的两边就是同时向内收 (ls[RootR],rs[RootL]) 或同时向外放 (ls[RootL],rs[RootR])，如果不这样的话遍历的两个位置本身就不对称。基于此，我们再来看实现。

实现

在代码实现方面，存树我们使用两个列表 ls 与 rs，这里开成了一个结构体，除此之外，我们还需要一个 id 用于存储树上节点的 value 。其余部分和思路部分所论述的一样。

代码

/*头文件及数组略*/

bool same(long long x, long long y) {
    if (x < 0 && y < 0) return true;     // 如果两边遍历到此处均为空，这棵树仍然对称
    if (x < 0 || y < 0) return false;    // 前面把都为空的情况return了，这里是只有一个点为空的情况
    if (t[x].id != t[y].id) return false;  // 值不匹配
    bool r = same(t[x].ls, t[y].rs)&&same(t[x].rs, t[y].ls);  // 递归检查子树是否符合要求
    return r;  // 略(?)
}

long long cnt(long long u) {  // 简单的节点统计
    if (u < 0) return 0;
    return cnt(t[u].ls)+cnt(t[u].rs)+1;
}

int main() {
    /* 输入略 */
    for (long long i = 1; i <= n; i++) {
        if (same(i, i)) {  // 如果以i为根的子树对称，统计节点并记录ans
            ans = max(ans, cnt(i));
        }
    }
    cout << ans;
    return 0;  // 结束
}