问一般树到二叉树的转换复杂度

EN

我不知道你说的“一般树”是什么意思无论如何，插入到平衡二叉树的复杂度是O(log n)，其中n是树中当前的项数，因此从某个项列表构建完整的树将是O(n log n)，其中n是要插入的项的总数。

您还必须包括从其他树中获取项目所需的时间。该时间取决于您拥有的树的类型。为了便于讨论，我假设您可以在线性时间内遍历它，因此从现有树中获取数据是O(n)。

这使得你的总时间复杂度为O(n + (n log n))。

所需的额外空间是n * sizeof(node)，其中sizeof(node)是二叉树节点的大小。请注意，如果存储在“通用树”节点中的项是指针，则不必支付复制实际对象的成本--只需支付二叉树节点的开销，这通常是三个指针:数据、左子链接和右子链接。