java - 将排序链表转换为平衡 BST

Question

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

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

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) 空间复杂度吗？

下面的算法也比“计算给定链表中的节点数”更好。令其为 n。计算节点后，我们取左 n/2 个节点并递归构造左子树。构造左子树后，我们为 root 分配内存并将左子树与 root 链接。最后，我们递归构造右子树并将其与 root 链接。在构建 BST 的同时，我们还不断将链表头指针移动到 next，以便我们有适当的指针每次递归调用”

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;
}

Answer 1

BST-构建

通过将列表分割为两个等长的列表，中间的一个元素用作根，可以从排序列表构建平衡树。例如:

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，因为所有较小的元素都是左子树的一部分，而所有较大的元素都是右子树的一部分。

慢 和快

您的代码使用两个迭代器工作，其中一个 (fast) 迭代节点的速度是另一个 (slow) 的两倍。因此，当 fast 到达尾部或列表尾部之前的节点时， slow 必须位于列表中间的节点，从而划分列表分成两个相同长度的子列表(最多有一个元素差异)，然后可以如上图所示递归处理。

运行时复杂度

该算法在 O(n lg n) 中运行。让我们从 helper 的循环开始:

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

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

应用Master-theorem (case 2) 对于上面的循环，我们得到 O(n lg n)。

空间复杂度

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

编辑

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