algorithm - 将排序的双向链表转换为 BST

Question

如何将已排序的双向链表转换为平衡二叉搜索树。

我正在考虑以与将数组转换为平衡 BST 相同的方式来执行此操作。 找到中心，然后递归转换DLL的左半部分和右半部分。 例如，

1 2 3 4 5 => 1 2 (3) 4 5 =>

     3
   /   \
  2     4
 /       \
1         5

这导致递归 T(n) = 2T(n/2) + O(n)。 O(n) 用于找到中心。 因此时间复杂度为 O(nlogn)。 我想知道是否有一种算法可以在 O(n) 中执行此操作。

Answer 1

是的，有 O(n) 的解决方案。请注意 in-order traversal在 BST 上，以所需的顺序迭代元素，因此只需对大小为 n 的初始空树进行中序遍历，然后用列表中的元素填充它。 [您在遍历中插入到树中的第 i 个元素是列表中的第 i 个元素]。
在答案的末尾，我添加了如何在 O(n) 中创建一个空的平衡树。

伪代码:[假设 |list| == |树|]

global current <- null
fillTree(tree,list):
  current <- list.head
  fillTree(tree)
fillTree(tree):
  if tree == null:
     return
  fillTree(tree.left)
  //in-order traversal: we set the value after setting left, and before calling right
  tree.val <- current.val
  current <- current.next
  fillTree(tree.right)

复杂度一般为 O(n)，因为树的每个顶点只有一次迭代，而每次迭代的复杂度为 O(1)。

编辑:
您可以创建一个空的平衡树，只需构建一个空的complete tree (*)，它是平衡的，构建它是 O(n)。

(*)完全二叉树是一棵二叉树，其中除了最后一层外，每一层都被完全填满。