конвертировать отсортированный связанный список в сбалансированный BST

Question

Я работаю над вопросом об интервью ниже:

Учитывая односвязный список, в котором элементы сортируются в порядке возрастания, преобразовать его в BST с балансировкой по высоте.

Для этой задачисбалансированное по высоте двоичное дерево определяется как двоичное дерево, в котором глубина двух поддеревьев каждого узла никогда не отличается более чем на 1.

Я пытаюсь понять приведенное ниже решение и его сложность?Может кто-нибудь помочь мне понять, как это работает?Ниже решения O (n) сложность времени и O (log n) сложность пространства?

Также ниже алгоритм лучше, чем «подсчет количества узлов в данном связанном списке. Пусть это будет n. После подсчета узлов мы берем n / 2 узлов слева и рекурсивно создаем левое поддерево. После левого поддеревасоздается, мы выделяем память для корня и связываем левое поддерево с корнем. Наконец, мы рекурсивно создаем правое поддерево и связываем его с корнем. При создании 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

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, так как все меньшие элементы являются частью левого поддерева и все более крупные элементы правого поддерева.

slow и fast

Ваш код работает с использованием двух итераторов, где один (fast) выполняет итерации по узлам в два раза быстрее, чем другой (slow).Поэтому, когда fast достигнет либо хвоста, либо узла непосредственно перед хвостом списка, slow должен находиться в узле в середине списка, таким образом, разделив список на два подсписка одинаковой длины (добольшая часть разницы в элементах), которая затем может быть рекурсивно обработана, как показано на приведенной выше диаграмме.

Сложность времени выполнения

Алгоритм работает в O(n lg n).Давайте начнем с повторения хелпера:

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

При каждом вызове helper мы должны найти средний узел связанного списка, определенный двумя параметрами, переданными в helper.Это может быть сделано только в n / 2 шагах, так как мы можем идти только линейно по списку.Кроме того, helper вызывается рекурсивно дважды для связанных списков, равных половине размера исходного списка для построения левого и правого поддерева.

Применение Мастер-теоремы (случай 2)с учетом приведенного выше повторения мы получаем O(n lg n).

Пространственная сложность

Пространственная сложность также должна принимать во внимание созданную структуру вывода.Поскольку каждый элемент связанного с входом списка преобразуется в узел в BST, сложность составляет O(n).

РЕДАКТИРОВАТЬ

Если выходные данные игнорируются, сложность пространства зависит исключительно от глубины рекурсии, которая, в свою очередь, составляет O(lg n), таким образом, делая пространство-сложность O(lg n).