在不改变结构的情况下将空二叉树填充为二叉搜索树（节点链接）
Filling empty Binary tree as Binary search tree without changing structure (Node linkage)
我今天参加了面试，被要求编写代码..
你有一个已经创建的无序二叉树，在任何节点中都没有数据。
我们有一个包含相同数量元素的数组。
我们必须在不改变二叉树结构的情况下，将数据作为二叉搜索树插入二叉树中。
我想出的方法是对数组进行排序，然后一个一个遍历它的元素，将每个数据元素放在树中第一个空的inorder节点中。
但我想这是不正确的，因为我没有被选中。
抱歉，算法题不允许。如果有这样的问题，我会把它记下来...
是对的，当你对数组进行排序，并按顺序将其放入不可改变的树中时，树就被正确填充了。
但也许有更好的方法来解决这个任务......没有排序，或者可能另一个问题是错误的......抱歉
您的解决方案不仅正确，而且不可能做得更好（在渐近意义上），假设数据项之间只允许 < 或 > 比较。
你的解决方案是对数据进行排序，耗时O(n log n)，然后按顺序遍历将其插入树中，耗时O(n)，总时间复杂度为O（n日志n）。注意，在构建二叉搜索树后，我们可以使用中序遍历将其所有数据按排序顺序读取出来——也就是说，解决面试官的问题可以用来排序任何给定的数据元素序列。
现在相反地假设实际上有一些算法可以在 o(n log n) 时间内解决面试官的问题——也就是说，时间复杂度比你给出的要好得多。然后，该算法可用于在严格优于 O(n log n) 的时间内对给定数据进行排序。但我们知道这是不可能的——O(n log n) 是排序 n 个元素所需时间的下限，如果我们被允许对它们做的只是使用 < 或 >。因此不存在这样更好的算法。
请注意，如果我们假设输入值是受某个常数限制的小整数，则此界限将不成立，因为那时像基数排序这样的操作可以在 O(n) 时间内执行排序。
我今天参加了面试，被要求编写代码.. 你有一个已经创建的无序二叉树，在任何节点中都没有数据。 我们有一个包含相同数量元素的数组。 我们必须在不改变二叉树结构的情况下，将数据作为二叉搜索树插入二叉树中。
我想出的方法是对数组进行排序，然后一个一个遍历它的元素，将每个数据元素放在树中第一个空的inorder节点中。 但我想这是不正确的，因为我没有被选中。
抱歉，算法题不允许。如果有这样的问题，我会把它记下来...
是对的，当你对数组进行排序，并按顺序将其放入不可改变的树中时，树就被正确填充了。 但也许有更好的方法来解决这个任务......没有排序，或者可能另一个问题是错误的......抱歉
您的解决方案不仅正确，而且不可能做得更好（在渐近意义上），假设数据项之间只允许 < 或 > 比较。
你的解决方案是对数据进行排序，耗时O(n log n)，然后按顺序遍历将其插入树中，耗时O(n)，总时间复杂度为O（n日志n）。注意，在构建二叉搜索树后，我们可以使用中序遍历将其所有数据按排序顺序读取出来——也就是说，解决面试官的问题可以用来排序任何给定的数据元素序列。
现在相反地假设实际上有一些算法可以在 o(n log n) 时间内解决面试官的问题——也就是说，时间复杂度比你给出的要好得多。然后，该算法可用于在严格优于 O(n log n) 的时间内对给定数据进行排序。但我们知道这是不可能的——O(n log n) 是排序 n 个元素所需时间的下限，如果我们被允许对它们做的只是使用 < 或 >。因此不存在这样更好的算法。
请注意，如果我们假设输入值是受某个常数限制的小整数，则此界限将不成立，因为那时像基数排序这样的操作可以在 O(n) 时间内执行排序。