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

· · 题解

建议在 博客 查看。

考虑如何求解树的对称性问题。

假如我们现在在 i 号结点，其左儿子为 l_i，右儿子为 r_i。

若 l_i 和 r_i 都为 -1，即都不存在，则以 i 为根的子树是对称的。

若 l_i 和 r_i 有一个为 -1，则以 i 为根的子树必定不是对称的。

剩下了 l_i 和 r_i 都不为 -1 的情况，即两棵子树都不为空。

若 i 是对称的，则 l_i 和 r_i 的子树大小必须相等（用来剪枝），并且 l[l_i] 和 r[r_i] 的子树相同，r[l_i] 和 l[r_i] 的子树相同。

如果递归中只记录一个变量，就不好处理。

在递归中记录两个变量，表示两边递归到的变量。

先判断为空的情况，再判断两个变量的 a 值是否相等，不是的话就一定不对称。

最后对于两棵子树不为空的情况，直接递归 (l[l_i], r[r_i]) 和 (r[l_i], l[r_i])。

如果加上大小的剪枝，就再写一个计算子树大小的 dfs 即可。

void dfs1(int x){//计算子树大小
    if(x == -1){
        return;
    }
    dfs1(l[x]);
    dfs1(r[x]);
    size[x] = 1 + size[l[x]] + size[r[x]];//自己 + 左子树 + 右子树
}
bool dfs2(int x, int y){
    if(size[x] != size[y]){//子树大小不相等
        return 0;
    }
    if(a[x] != a[y]){//值不相等
        return 0;
    }
    if((x == -1) && (y == -1)){//两个子树为空
        return 1;
    }
    if((x == -1) || (y == -1)){//子树有一个为空
        return 0;
    }
    return dfs2(l[x], r[y]) && dfs2(r[x], l[y]);//向下递归
}
int main(){
    dfs1(1);
    for(int i = 1; i <= n; ++ i){
        if(dfs2(i, i)){//根为 i 的子树是对称的
            ans = max(ans, size[i]);
        }
    }
}