N-ary树 - 是对称的还是不对称的

Question

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

Answer 1

考虑这个问题的一种方法是注意树是对称的,如果它是自己的反射,树的反射是递归定义的:

1. 空树的反射本身就是.
2. 具有根r和子c1,c2,...,cn的树的反射是具有根r的树,并且子反射(cn),...,反射(c2),反射(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),但很可能更好.