将空二进制树填充为二进制搜索树而不更改结构(节点链接)

Question

今天我接受了一次采访,我被要求对此进行编码..你已经创建了一个无序的二叉树,任何节点都没有数据.我们有一个具有相同数量元素的数组.我们必须在二叉树中插入数据作为二叉搜索树而不改变二叉树的结构.

我想出的方法是对数组进行排序,然后逐个遍历其元素,将每个数据元素放在树中的第一个空的inorder节点中.但我猜这是不正确的,因为我没有被选中.

很抱歉,如果不允许算术问题.如果有这样的问题我会把它拿下来......

Answer 1

假设数据项之间只允许<或进行比较，您的解决方案不仅是正确的，而且不可能做得更好（在渐近意义上） 。>

您的解决方案包括对数据进行排序，这需要时间 O(n log n)，然后以中序遍历的方式将其插入到树中，这需要时间 O(n)，总体时间复杂度为 O(n log n) ）。请注意，在构建二叉搜索树之后，我们可以使用中序遍历按排序顺序读出其所有数据——也就是说，解决面试官的问题可以用于对任何给定的数据元素序列进行排序。

现在假设相反，实际上有某种算法可以在 o(n log n) 时间内解决面试官的问题 - 也就是说，其时间复杂度比您给出的算法严格更好。然后，该算法可用于严格优于 O(n log n) 时间对给定数据进行排序。<但我们知道这是不可能的——如果我们只允许使用or来比较它们，那么 O(n log n) 是对 n 个元素进行排序所需时间的下限>。因此，不存在这样更好的算法。

请注意，如果我们假设输入值是受某个常量限制的小整数，则此界限将无法成立，因为像基数排序这样的操作可以在 O(n) 时间内执行排序。