将排序链表转换为平衡BST

Question

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

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

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

平衡树可以从排序的列表中构造，方法是将列表细分为两个等长的列表，中间的一个元素用作根。例如：

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必须位于列表中间的节点，从而将列表分成两个子列表，长度相同（最多差一个元素），然后可以如上图所示对其进行递归处理。

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

如果忽略输出，则空间复杂度仅依赖于递归深度，递归深度为O(lgn)，从而使得空间复杂度O(lgn)。