将排序链表转换为平衡BST [英] convert Sorted Linked List to Balanced BST

问题描述

我正在处理以下面试问题：

I am working on below interview question:

给出一个单链列表，其中元素以
的升序排序，将其转换为高度平衡的BST。

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

对于此问题，高度平衡的二叉树被定义为二元
树，其中两个树的深度每个节点的子树之间的
相差不超过1。

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

我想了解以下解决方案及其复杂性吗？有人可以帮助我了解其运作方式吗？下面的解是否为O（n）时间复杂度和O（log n）空间复杂度？

I am trying to understand below solution and its complexity? Can someone help me understand how it works? Is below solution O(n) time complexity and O(log n) space complexity?

下面的算法也比计算给定链表中的节点数更好。取n。在计算节点数后，我们取n / 2个节点，递归构造左子树。构造左子树后，我们为根分配内存，并将左子树与根链接。最后，我们递归构造右子树并与根链接。在构造BST时，我们还继续移动列表指向下一个的头指针，以便我们在每个递归调用中都有合适的指针。

Also is below algorithm better than "counting the number of nodes in the given Linked List. Let that be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we allocate memory for root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root. While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call"

public TreeNode toBST(ListNode head) {
    if(head==null) return null;
    return helper(head,null);
}
public TreeNode helper(ListNode head, ListNode tail){
    ListNode slow = head;
    ListNode fast = head;
    if(head==tail) return null;

    while(fast!=tail && fast.next!=tail){
        fast = fast.next.next;
        slow = slow.next;
    }
    TreeNode thead = new TreeNode(slow.val);
    thead.left = helper(head,slow);
    thead.right = helper(slow.next,tail);
    return thead;
}

推荐答案

BST构造

可以通过将列表细分为两个等长的列表，并以中间的一个元素作为根，从排序后的列表中构造出一棵平衡树。例如：

BST-construction

A balanced tree can be constructed from a sorted list by subdividing the list into two equally long lists with one element in the middle being used as a root. E.g.:

1.                       [1, 2, 3, 4, 5, 6, 7]


2.                               4
                           /           \
                       [1, 2, 3]     [5, 6, 7]


3.                               4
                            /          \
                           2           6
                          / \         / \
                          1  3        5  7

即使两个子列表相差一个元素，它们的高度最多也可以相差1。 ，从而使树平衡。通过使用列表的中间元素，可以保证生成的树是BST，因为所有较小的元素都是左子树的一部分，而所有较大的元素都是右子树的所有元素。

Even if the two sublists differ by one element, they can at most differ by 1 in their height, thus making the tree balanced. By taking the middle element of the list the resulting tree is guaranteed to be a BST, since all smaller elements are part of the left subtree and all larger elements of the right subtree.

您的代码可以使用两个迭代器，其中一个（ fast ）在节点上迭代的速度是另一个迭代器（ slow ）的两倍。因此，当 fast 到达列表的尾部或尾部之前的节点时， slow 必须位于列表的尾部。列表中间的节点，因此将列表分为两个相同长度的子列表（最多不超过一个元素），然后可以如上图所示进行递归处理。

Your code works using two iterators, where one (fast) iterates over nodes twice as fast as the other (slow). So when fast has reached either the tail or the node right before the tail of the list, slow must be at the node in the middle of the list, thus dividing the list into two sublists of same length (up to at most one element difference), which can then be recursively processed as shown in the above diagramm.

该算法在 O（n lg n）中运行。让我们从辅助程序的重复开始：

The algorithm runs in O(n lg n). Let's start with the recurrence of helper:

T(n) = n / 2 + 2 * T(n / 2)
T(1) = 1

在每次调用 helper ，我们必须找到由传递给 helper 的两个参数定义的链表的中间节点。这只能通过 n / 2 步来完成，因为我们只能线性浏览列表。此外， helper 在原始列表大小的一半的链表上递归调用两次，以构建左右子树。

In each call of helper, we must find the middle-node of the linkedlist defined by the two parameters passed to helper. This can only be done in n / 2 steps, since we can only walk linearly through the list. In addition, the helper is called recursively twice on linkedlists of half the size of the original list to build the left and right subtree.

将主定理（案例2）应用于上述内容重复，我们得到 O（n lg n）。

Applying the Master-theorem(case 2) to the above recurrence, we get O(n lg n).

空间复杂性还需要考虑产生的产出结构。由于输入链接列表的每个元素都转换为BST中的一个节点，因此复杂度为 O（n）。

Space-complexity also needs to take the produced output-structure into account. Since each element of the input-linked list is converted into a node in the BST, the complexity is O(n).

编辑

如果忽略输出，则空间复杂度仅取决于递归深度，而递归深度又是 O（lg n），因此使空间复杂度 O（lg n）。

If the output is ignored, the space-complexity is solely dependent on the recursion-depth, which in turn is O(lg n), thus making the space-complexity O(lg n).

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