Обратный порядок в двоичном дереве поиска с использованием Iterator & Stack - ПРОБЕЛ сложности O (log N)? Как?

Question

Во время телефонного интервью меня попросили внедрить обход в порядке бинарного дерева поиска, используя Iterator & Stack ( не рекурсивно ).Мне не разрешили использовать родительский указатель.

Это начальный код, который мне дали.

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}};

class BTIterator
{
public:
    BTIterator(TreeNode *root){


    };
    TreeNode* next() {

    }
    bool hasNext() {

    }

};

Функция тестирования:

void TestFunc(TreeNode *root) {
BTIterator bti(root);
while(bti->hasNext()) {
  cout << bti->next()->val << " ";
}}

Я был специальнопопросили реализовать BTIterator, next, hasNext в приведенном выше коде.

Так я и сделал.Последующие вопросы были каковы время и пространство сложности.Поэтому я ответил, что время O (N), пространство O (N).Однако интервьюер сказал: «Вы можете уменьшить сложность пространства до O (log N)».Я спросил его, как, и он сказал: «Нам нужно только хранить родителей».(Я мог бы услышать его неправильно. У него был очень сильный акцент.) Моя реализация хранила все узлы, которые оставили детей.Я просто воспринял его ответ как должное.

Однако после интервью, я думаю, даже если нам нужно только сохранить родителей (не листовой узел), это все равно O (N).Это точный O (N / 2), но это все еще O (N).Я считаю, любой узел, который оставил дочерние элементы , должен храниться в стеке.Как не делать?

Единственный раз, когда можно достичь пробела O (logN), это когда двоичное дерево имеет только одну ветвь, которая продолжает работать (не сбалансированное дерево с полными листьями.)

Что мне здесь не хватает?Если кто-нибудь может объяснить, как сложность пространства с помощью итератора может быть уменьшена до O (log N), я буду очень признателен!

Answer 1

Мне кажется, я понимаю ваше замешательство.

Рассмотрим это дерево (просто у нас есть конкретный пример, на который можно сослаться):

         A
       /   \
      B     C
     / \   / \
    D   E F   G

В течение итерации по этому дереву вам нужно будет хранить каждый отдельный узел с левым дочерним элементом & mdash; три узла A, B и C. В целом, для любого дерева вам нужно хранить до O ( n ) узлов в течение вашей итерации. Похоже, поэтому вы говорите O ( n ).

Но вам не нужно хранить все эти узлы одновременно . После того как вы перешли на E, вам больше не нужно хранить узел B для чего-либо. В любой данный момент итерации вам нужно только сохранить позже предков current node & mdash; это не более двух узлов, а именно A и B (когда ваш текущий узел D). В целом, для любого дерева вам никогда не понадобится хранить более O ( h ) одновременно, где h - высота дерево. Предполагая сбалансированное дерево (как, очевидно, говорит ваш интервьюер), это означает O (log n ).

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

Answer 2

Если дерево двоичного поиска (BST) не сбалансировано, и мы должны использовать метод стека, то O(h) - это сложность пространства, где h - высота данного BST.По-видимому, невозможно добиться большей сложности пространства, если использовать метод стека.

Если данный BST сбалансирован или если вам разрешено его балансировать, то это возможнодля достижения O(logn) сложности пространства, где n - это количество узлов в данном BST.

Очевидно, что если вы не обязаны использовать метод стека, вы можете поиграть с компромиссами времении космическая сложность.Если разрешена предварительная обработка, используйте обход в порядке Морриса с использованием потоков для O(n) дополнительного пространства и O(1) сложности времени.Кроме того, если предварительная обработка не разрешена, вы можете просто сохранить current TreeNode.Когда вызывается next(), найдите наименьшую верхнюю границу сохраненного текущего TreeNode за O(logn) время для сбалансированного BST и за O(n) время для несбалансированного BST.Обновите current до возврата с next().Таким образом, вы можете обменять время на O(1) космическую сложность.