如何在二叉搜索树中找到节点的第n个祖先?

在搜索节点时,可以跟踪从当前节点到根节点路径中的所有节点。这是一个长度不大于树的深度的简单列表。一旦找到节点,它的 n 祖先已经就位 长度n 在列表中。

我想你的问题有点错。你错过了一件重要的事情。你当然可以不用第二关。只要保持一个 queue 在搜索的最后n个节点中。

你错过的是这样的算法需要 O(log n) 记忆。当你的解决方案用时间来换取内存使用时, O(1) (恒定量)附加内存)

所以你的解决方案不是“错误”或“太慢”。它有自己的利弊。

嗯,我突然想到,一个简单的方法,只需要一个额外的节点或更少的空间将是有一个虚拟节点,持有回溯计数。找到搜索目标后,将虚拟节点设置为 n 并返回 它 ,而不是找到不需要的节点。

你需要一个函数 DUMMY(node) 仅对虚拟节点返回true。( DUMMY() 可以通过比较节点地址或通过检查节点内的magic 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 祖先)。

为此,请使用n个间隔的队列。每当你找到一个,德克和恩克,

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);
}

是的,不用第二遍就可以完成。你只需要用两个指针。你可以这样做

1. 使用指针p1,从根开始,搜索要找到其祖先的节点。但你只走了N步。
2. 现在,当您向下到达n步时,从根开始另一个指针p2,它也会搜索同一个节点。
3. 按锁定步骤移动两个指针,使它们一起向下移动一层。当p1到达节点时,p2将指向第n个祖先。

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;
}
}

其背后的逻辑是,我们通过递归从根节点一直到搜索节点,当我们找到它时,我们沿着它来自的路径遍历并打印它。