Как найти n-го предка узла в бинарном дереве поиска?

Question

Меня спросили об этом на собеседовании. Вот мое O(log n) решение.

Найти глубину узла. Повторите поиск, но остановитесь на depth - n.

Есть ли способ сделать это без второго прохода?

Answer 1

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

Answer 2

Используйте для этого n-интервальную очередь. Всякий раз, когда вы найдете один, deque и enque,

findnth(node *root, queue q, int n, int number)
{
   if(!root || !q) 
      return;
   findnth(root->left,  q, n, number);
   if(root->d == number) {
      if(q.size() < n) {
         nth ancestor not exist;
         print q->deq() as q.size() ance return;
      }
      else
         print q.deq()
   }
   if(q.size() < n) {
      q.ins(node->data);
   }
   else {
      q.deq();q.enq(node->data);
   }
   findnth(root->right,  q, n, number);
}

Answer 3

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

Вам нужна функция DUMMY(node), которая возвращает true только для фиктивного узла. (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;
}

Answer 4

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

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

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

Answer 5

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

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 th предка).

Answer 6

I think this function might help ... 

function printAncestor(node *root , node *search , int *k)
{
  if(!root)
   return 0;
  if(root == search)
   return 1;

  int p1 ,p2;
  p1 = printAncestor(root->left , search , k);
  p2 = printAncestor(root->right , search , k);

 if(p1) {
   (*k)--;
if(*k >0)
   printf("%d ",root->left->value);
return 1;
 }
if(p2)
{
  (*k)--;
  if(*k >0)
  printf("%d ",root->right->value);
return 1;
}
}

Логика, стоящая за этим, заключается в том, что мы идем до узла поиска из корня посредством рекурсии. Когда мы находим его, мы проходим по пути, с которого он пришел, и печатаем его.

Answer 7

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

1. Используя указатель p1, начиная с корня, найдите узел, предок которого нужно найти. Но вы идете только на n шагов вниз.
2. Теперь, когда вы достигнете n шагов вниз, запустите еще один указатель p2 из корня, который также ищет тот же узел.
3. Переместите оба указателя в шаге блокировки так, чтобы они оба вместе опустились на один уровень вниз. Когда p1 достигнет вашего узла, p2 укажет на n-го предка.