Как я нахожу энного предка узла в дереве двоичного поиска?

При поиске узла вы можете отслеживать все узлы на пути от текущего узла до корня. Это простой список, длина которого не превышает глубины дерева. Как только узел будет найден, его n -й предок окажется на позиции length - n в списке.

Думаю, ваш вопрос немного неправильный. Вы упускаете одно важное дело. Конечно, можно и без второго прохода. Просто поддерживайте очередь из последних n узлов в вашем поиске.

Вы упускаете то, что такому алгоритму требуется O (log n) памяти. В то время как ваше решение жертвует затратами времени на использование памяти и использует O (1) (постоянный объем) дополнительной памяти)

Таким образом, ваше решение не «неправильное» или «слишком медленное». У него просто есть свои плюсы и минусы.

Хм, мне пришло в голову, что простой способ, для которого требуется только один дополнительный узел или меньше в пространстве, - это иметь фиктивный узел, содержащий счетчик обратных отсчетов. Когда вы найдете цель поиска, вы затем установите фиктивный узел на n и верните это , а не найденный вами узел, который вам не нужен.

Вам нужна функция DUMMY (узел) , который возвращает истину только для фиктивного узла. ( DUMMY () может быть реализован путем сравнения адреса узла или проверки наличия волшебного файла cookie внутри узла.)

Node *search(Node *next) {
  if (found the the answer)
    dummy->backtrack = n;
    return dummy;
  } else r = search(whatever ? n->left : n->right);
  if (DUMMY(r)) {
    if (dummy->backtrack == 0)
      return next;
    --dummy->backtrack;
  }
  return r;
}

Просто найдите узел и сохраните путь, следуя по нему. Примерно это (для дерева целых чисел):

Node* nthAncestor(Node* root, int target, int n)
{
    Node* list[n];
    int pos = 0;
    Node* node = root;
    while(node->value != target)
    {
        list[pos] = node;
        pos = (pos + 1) % n;
        if(node->value < target)
            node = node->left;
        else if(node->value > target)
            node = node->right;
    }

    return list[(pos + 1) % n];
}

Обратите внимание, что я предположил, что n-й предок действительно существует .

Для дерева размера T это выполняется за O (log T) время и использует O (n) пробел ( n как в n -й предок).