转换一个有序双向链表到BST [英] Converting a sorted doubly linked list to a BST

问题描述

如何能排序双向链表被转换成一个平衡的二叉查找树

How can a sorted doubly linked list be converted to a balanced binary search tree.

我在想这样做同样的方式将阵列来平衡BST的。 找到中心，然后递归转换的左侧部分和DLL的右侧部分。 例如，

I was thinking of doing this the same way as converting an array to a balanced BST. Find the centre and then recursively convert the left part and the right part of the DLL. For example,

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）。

This is leads to the recurrence T(n) = 2T(n/2) + O(n). O(n) is for finding the centre. The time complexity is therefore O(nlogn). I was wondering if there is an algorithm that does this in O(n).

推荐答案

是有O（n）的解决方案。请注意，中序遍历在BST，是迭代所需顺序的元素，所以才做了一个序遍历的大小为n 的初始为空树，并在列表中的元素填充它。 [插入到树的遍历第i个元素，在列表中的第i个元素。
在回答结束时，我加了如何创建一个空的平衡树 O（N）。

Yes there is O(n) solution. Note that an in-order traversal on a BST, is iterating the elements in the desired order, so just do an inorder traversal on an initially empty tree of size n, and fill it with elements in the list. [The i'th element you insert to the tree in your traversal, is the i'th element in the list].
At the end of the answer I added how to create an empty balanced tree in O(n).

伪code ：假设|列表| == |树|]

pseudocode: [assuming |list| == |tree|]

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），因为有excactly一次迭代的树的每个顶点，并且每次迭代是O（1）。

Complexity is trivially O(n), since there is excactly one iteration for each vertex of the tree, and each iteration is O(1).

编辑：
可以创建一个空的平衡树，只需建立一个空的完整的树（*），它是平衡的，建设它是O（n）。

You can create an empty balanced tree, by simply building an empty complete tree(*), it is balanced and building it is O(n).

（*）完全二叉树是二叉树中，每个级别的，可能除了最后一个，完全充满。

(*)A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled.

这篇关于转换一个有序双向链表到BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！