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

Question

我在一次职业面试中被问到了这个问题，下面是我的 O(log n) 解决方案。

找到节点的深度。 重复搜索，但在 depth - n 处停止。

有没有办法在不进行第二遍搜索的情况下完成这个问题呢？

- sigjuice

---

记住最后的n个节点。 - Gumbo

你把 n 和树中的项目数量混在一起了。这是有意为之吗？ - P Shved

请注意，在很多情况下，面试问题是故意不正确或不完整地表述的，目的是为了看看你是否能够找出问题并提出正确的问题，而不是急于编写代码。根据上述问题陈述（假设你已经准确重现它），任何坚持要求具体代码作为解决方案的人都会自动失败这个问题。 - AnT stands with Russia

问题陈述过于模糊，无法得出具体的解决方案。在澄清问题之前，这里给出的任何解决方案都是完全猜测（可能是不相关的）。缺失的关键部分包括：1）节点是按其键还是按物理指针指定的，2）树中是否存在子->父链接。可以安全地假设答案为2是“否”（否则，问题将过于琐碎），但是如果没有对1的具体答案，甚至开始解决问题都毫无意义。 - AnT stands with Russia

@AndreyT：我想我应该提到节点是由其键指定的。 - sigjuice

Answer 1

在查找节点时，您可以跟踪从当前节点到根节点的所有节点路径。这是一个简单的列表，长度不大于树的深度。一旦找到节点，它的第n个祖先位于列表中的位置为length - n。

- Stephan202

Answer 2

使用一个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);
}

- vikas

Answer 3

只需查找节点并在跟随它时保存路径。 大致如下（对于整数树）：

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 个祖先）。

- R. Martinho Fernandes

---

while后面的分号是有意为之吗？ - Gumbo

显然这不是故意的。谢谢Gumbo。 - R. Martinho Fernandes

Answer 4

嗯，我想到了一个简单的方法，只需要一个额外的节点或更少的空间，就可以有一个虚拟节点来保存回溯计数。当你找到搜索目标时，你可以将虚拟节点设置为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;
}

- DigitalRoss

---

从技术上讲，这并不仅仅使用了一个额外节点的空间...你忘记了递归中使用的堆栈空间。 - R. Martinho Fernandes

呵呵，好的，我想我本可以说“额外”的空间。 - DigitalRoss

Answer 5

你的问题有点错误，我猜测你漏掉了一个重要的事项。当然你可以不用第二次遍历来完成它。只需维护一个队列，包含你搜索的最后n个节点。

你忽略的是这种算法需要O(log n)的内存。而你的解决方案则是以时间消耗为代价，使用O(1)（恒定数量）的额外内存。

所以你的解决方案并不是“错误”或“太慢”。它只是有其优缺点。

- P Shved

---

队列可能比这更糟，对于一个完全不平衡的树，它已经退化成一个链表，需要O(n)的时间。如果您可以接受潜在的O(n)内存消耗，您也可以考虑使用大小为N的平面数组来保存遍历历史记录。这也避免了在到达目标后查找第k个祖先所需的O(N)（对于单向链表）或O(k)（对于双向链表）遍历。 - Matt J

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

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

- Flash

Answer 7

是的，可以在不进行第二次遍历的情况下完成。您只需要使用两个指针即可。以下是如何实现：

1. 使用指针p1，从根节点开始搜索要查找祖先的节点。但是，您只需向下走n步。
2. 现在，当您到达n步时，从根节点开始启动另一个指针p2，也搜索相同的节点。
3. 将两个指针锁定并一起向下移动，使它们同时下降一级。当p1到达您的节点时，p2将指向第n个祖先。

- Sachin