algorithm - N-ary树 - 它是否对称

Question

给定一棵 N 叉树，找出它是否关于通过树的根节点绘制的线对称。在二叉树的情况下很容易做到这一点。然而对于N元树来说似乎很难

Answer 1

思考这个问题的一种方法是注意如果树是它自己的反射，那么树是对称的，其中树的反射是递归定义的:

1. 空树的倒影就是它自己。
2. 具有根 r 和子节点 c1, c2, ..., cn 的树的反射是具有根 r 和子节点 reflect(cn), ..., reflect(c2), reflect(c1) 的树。

然后您可以通过计算树的反射并检查它是否等于原始树来解决此问题。这又可以递归完成:

1. 空树只等于它自己。
2. 一棵有根 r 和子节点 c1, c2, ..., cn 的树等于另一棵树 T 当且仅当另一棵树是非空的，有根 r，有 n 个子节点，并且有等于 c1, . .., cn 按此顺序。

当然，这有点低效，因为它在进行比较之前制作了树的完整副本。内存使用量为 O(n + d)，其中 n 是树中的节点数(用于保存副本)，d 是树的高度(用于保存递归中的堆栈帧以检查是否相等)。由于 d = O(n)，这使用 O(n) 内存。但是，它的运行时间为 O(n)，因为每个阶段只访问每个节点一次。

一种更节省空间的方法是使用以下递归公式:

1. The empty tree is symmetric.
2. A tree with n children is symmetric if the first and last children are mirrors, the second and penultimate children are mirrors, etc.

然后您可以定义两棵树作为镜像，如下所示:

1. 空树只是它自己的一面镜子。
2. 具有根 r 和子节点 c1, c2,..., cn 的树是具有根 t 和子节点 d1, d2, ..., dn 的树的镜像，当且仅当 r = t, c1 是 dn 的镜像, c2是dn-1的镜像等

此方法也在线性时间内运行，但不会生成树的完整副本。因此，内存使用量仅为 O(d)，其中 d 是树的深度。这在最坏的情况下是 O(n)，但很可能要好得多。