Как построить двоичное дерево поиска снизу вверх

Question

Учитывая отсортированный массив, очень легко визуализировать BST из него сверху вниз. Например, если массив равен [1,2,3,4,5,6,7], мы можем видеть, что корень будет средним элементом, то есть 4. Слева от него будет поддерево, корень которого находится в середине среза массива слева от 4, то есть 2. Точно так же он будет аналогичным и в праве.

Как мы можем сделать эту визуализацию для восходящего подхода к построению BST? В основном я пытаюсь понять алгоритм построения BST из отсортированного связанного списка, который принимает O(N) снизу вверх, а O(Nlog N) - сверху вниз. Поэтому мне нужно понять, как он восходит снизу вверх.

Answer 1

Рассмотрим: http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) { 
    if (start > end) return NULL; 
    // same as (start+end)/2, avoids overflow 
    int mid = start + (end - start)/2; 
    BinaryTree *leftChild = sortedListToBST(list, start, mid-1); 
    BinaryTree *parent = new BinaryTree(list->data); 
    parent->left = leftChild; 
    list = list->next; 
    parent->right = sortedListToBST(list, mid+1, end); 
    return parent; 
} 

BinaryTree* sortedListToBST(ListNode *head, int n) { 
    return sortedListToBST(head, 0, n-1); 
} 

Выпишем некоторые из рекурсивных вызовов:

0 1 2 3 4 5 6 7 8 -> sortedListToBST(list, 0, 3) [A] 
0 1 2 3   -> sortedListToBST(list, 0, 0) [B] 
0     -> sortedListToBST(list, 0, -1) [C] 
*     -> NULL [D] 

[D] вернется NULL.

Теперь, в [C], у нас будет leftChild = NULL и parent = 0 (первый узел в списке). Левый дочерний элемент родителя будет NULL, и список будет прогрессирован. [C] затем позвонит sortedListToBst(1, 0), который вернет NULL, поэтому правый ребенок parent также будет NULL. Ваше дерево до сих пор выглядит следующим образом:

 0 
    / \ 
    null  null 

Теперь это будет возвращено на левый вызов в [B], так leftChild = 0 = the above в [B]. parent в [B] установит себя в 1 (второй узел в списке, обратите внимание, что мы продвинули головку списка в предыдущем вызове - список глобально/передан по ссылке). Его левый дочерний элемент будет установлен на то, что вы вычисляете на предыдущем шаге (приведенное выше дерево). Ваше дерево теперь выглядит следующим образом:

 1 
    /
    0 
/ \ 
null null 

Список продвигается снова, указывая на 2. Рекурсивный вызов sortedListToBST(list, 2, 3) будет сделан из [B], что вызовет несколько рекурсивных вызовов.

Это много, чтобы написать/объяснить, но, надеюсь, это приведет вас к правильному пути. На бумаге должно быть проще следовать.