1

最近，我在二叉树上遇到了这个问题：

  1. 给定一些任意的非平衡树，用什么大 O 来确定它是否是单值（所有元素都是相同的值）。

  2. 在上述情况下，平衡树还是线性树，哪个会导致最糟糕的大 O 复杂度？

这是我对这个问题的回答：

  1. 要确定一棵树是否是单值的，我们必须检查每个节点。因此，复杂度为 O(n)。

  2. 无论是线性树还是平衡树，如果它们具有相同数量的节点，就会有相同数量的比较。因此，复杂性将是相同的。

这个对吗？

4

1 回答 1

2

如果给定一棵任意二叉树，在最坏的情况下，您必须检查所有节点以确定它们是否具有相同的值。您可以在这里使用一个简单的对抗性参数 - 如果您的算法不查看所有值，因为树中任何不同的值之间没有关系，对手可以为您提供 n - 1 个值都相同的树。如果您没有查看最后一个值，则对手可能会通过将该值设置为与您的算法所说的相反来迫使您的算法出错。

另一方面，如果您谈论的是二叉搜索树，那么您可以在 O(h) 时间内解决这个问题，其中 h 是树的高度。具体来说，只需查看第一个和最后一个值，看看它们是否相同。如果是这样，则树中的所有中间值必须相同。如果不是，那么您已经见证了两个不同的价值观。这将在完美平衡的树上运行时间 O(log n)，在退化链表上运行时间为 O(n)。我怀疑这可能是最初的问题要问的问题，因为它比一般的二叉树案例更有趣（至少在我看来）。

希望这可以帮助！

于 2014-05-22T16:03:08.193 回答