4

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

4

5 回答 5

6

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

  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 是树的高度（保存递归 tom 检查中的堆栈帧是否相等）。由于 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)，但很可能要好得多。

于 2011-01-31T20:38:44.987 回答
1

我只会在左子树上进行有序树遍历（节点左右）并将其保存到列表中。然后在右子树上进行另一个有序树遍历（节点右左），并将其保存到一个列表中。然后，您可以只比较这两个列表。他们应该是一样的。

于 2011-12-24T09:45:17.380 回答
0

取一个堆栈 现在每次开始遍历根节点，现在递归调用一个函数，并将左子树的元素一个一个地压入特定级别。维护一个全局变量并在每次将左子树推入堆栈时更新其值。现在递归调用（在递归调用左子树之后）右子树并在每个正确匹配时弹出。这样做将确保它正在以对称方式检查。

最后，如果堆栈为空，即所有元素都被处理并且堆栈的每个元素都被弹出......你通过了！

于 2011-10-10T18:25:33.437 回答
0

回答这个问题的另一种方法是查看每个级别，看看每个级别是否是回文。对于 Null 节点，我们可以继续添加具有唯一值的虚拟节点。

于 2020-08-05T14:12:05.530 回答
-1

这并不难。我要带着这个问题打高尔夫球。我得了 7 分……有人好点了吗？

data Tree = Tree [Tree]
symmetrical (Tree ts) =
    (even n || symmetrical (ts !! m)) &&
    all mirror (zip (take m ts) (reverse $ drop (n - m) ts))
    where { n = length ts; m = n `div` 2 }
mirror (Tree xs, Tree ys) =
    length xs == length ys && all mirror (zip xs (reverse ys))
于 2010-02-23T04:50:33.750 回答