在某些测试用例中，寻找最小共同祖先的代码无法使用。

Question

我正在做这个来自Hackerrank的练习(https:/www.hackerrank.comchallengesbinary-search-tree-lowest-common-ancestorcopy-from158548633)在这个练习中，我们得到一个指向二进制搜索树根的指针和两个值。v1 和 v2. 我们需要返回最低的共同祖先（LCA）的。v1 和 v2 在二进制搜索树中，我们必须完成函数 lca. 它应该返回一个指向所给两个值的最低公共祖先节点的指针。

lca有以下参数。

• root：指向二进制搜索树根节点的指针。

• v1：一个节点.数据值

• v2：一个节点.数据值

我知道递归的解决方案比较简单，但是我试过这个方法，找不到任何测试用例失败的原因。下面提到的解决方案只通过了610个测试用例。我无法看到所有4个失败的测试用例，但我可以提到1个测试用例。

下面是我的代码

/*The tree node has data, left child and right child 
class Node {
    int data;
    Node* left;
    Node* right;
};

*/

vector<Node*> find(int v, Node* root)

{
    vector<Node*> ar;
    if (v == root->data) {

        ar.push_back(root);
        return ar;
    }

    if (v > root->data) {
        ar.push_back(root);
        find(v, root->right);
    }

    if (v < root->data) {
        ar.push_back(root);
        find(v, root->left);
    }
    ar.push_back(root);
    return ar;
}

Node* lca(Node* root, int v1, int v2)
{

    //this vector contains the nodes in path
    //to reach from root to node
    vector<Node *> a, b;

    //find function return the vector
    a = find(v1, root);
    b = find(v2, root);

    //index of the LCA in the vector
    int res = 0;

    //traversing the two vectors from
   //beg to end if two nodes are same
  //update the value of res. Final updated
 //value will give us LCA
    int n = b.size();
    if (a.size() < b.size())
        n = a.size();
    int i = 0;
    while (i < n) {
        if (a[i] == b[i])
            res = i;

        i++;
    }
    return a[res];
}

不合格的测试案例。

8

8 4 9 1 2 3 6 5

1 2

预期产出：1

1

我的输出。

8

需要帮助来调试代码，并找到这种方法的漏洞。

Answer 1

下面的伪代码可以用来生成LCA问题的代码。

/////////

递归调用LCA函数，左子树和右子树各调用一次。如果节点为null，则返回简单的null，否则返回

如果node的值等于v1、v2中的任何一个值，那么只需返回这个节点。

否则对子树进行递归调用。

现在当你收到2次递归调用的结果时，检查-&gt。

如果两个都是null，那么返回null

如果一个是空的，另一个不是空的，那么返回非空节点。

如果两者都不为空，则返回根音本身。

Answer 2

你的算法不能工作

• 在 找到 递归调用产生的向量会丢失，所以你不做这些调用，最后你只得到初始调用产生的向量。
• 在 lca 就算 找到 做正确的事情，你认为答案它在。一样 在2个向量中的排名，为什么？

一种方法是 。

Node * Node::lca(int v1, int v2) {
  if ((data == v1) || (data == v2))
    return this;

  Node * r = (right == NULL) ? NULL : right->lca(v1, v2);
  Node * l = (left == NULL) ? NULL : left->lca(v1, v2);

  return ((r != NULL) && (l != NULL))
    ? this
    : ((r == NULL) ? l : r);
}

---

一个完整的例子。

#include <iostream>
#include <vector>
#include <iomanip>

class Node {
  private:
    int data;
    Node* left;
    Node* right;

  public:
    Node(int d) : data(d), left(NULL), right(NULL) {}
    void insert(int d);
    void draw(int level = 1) const;
    Node * lca(int v1, int v2);
};

void Node::insert(int d) {
  Node * n = new Node(d);
  Node * t = this;

  for (;;) {
    if (d > t->data) {
      if (t->right == NULL) {
        t->right = n;
        return;
      }
      t = t->right;
    }
    else if (t->left == NULL) {
      t->left = n;
      return;
    }
    else
      t = t->left;
  }
}

void Node::draw(int level) const {
  if (right != NULL)
    right->draw(level + 1);
  else
    std::cout << std::setw(level + 1) << '/' << std::endl;

  std::cout << std::setw(level) << data << std::endl;

  if (left != NULL)
    left->draw(level + 1);
  else
    std::cout << std::setw(level + 1) << '\\' << std::endl;
}

Node * Node::lca(int v1, int v2) {
  if ((data == v1) || (data == v2))
    return this;

  Node * r = (right == NULL) ? NULL : right->lca(v1, v2);
  Node * l = (left == NULL) ? NULL : left->lca(v1, v2);

  return ((r != NULL) && (l != NULL))
    ? this
    : ((r == NULL) ? l : r);
}

int main()
{
  Node r(8);
  std::vector<int> v = { 4, 9, 1, 2, 3, 6, 5 };

  for (auto d : v) 
    r.insert(d);

  r.draw();

  std::cout << "----------------" << std::endl;

  Node * l;

  std::cout << "lca for 1 & 2" << std::endl;
  l = r.lca(1, 2);
  if (l != NULL) 
    l->draw();

  std::cout << "----------------" << std::endl;

  std::cout << "lca for 5 & 2" << std::endl;
  l = r.lca(5, 2);
  if (l != NULL) 
    l->draw();
}

编译和执行。

pi@raspberrypi:/tmp $ g++ -Wall lca.cpp 
pi@raspberrypi:/tmp $ ./a.out
  /
 9
  \
8
   /
  6
    /
   5
    \
 4
     /
    3
     \
   2
    \
  1
   \
----------------
lca for 1 & 2
   /
  3
   \
 2
  \
1
 \
----------------
lca for 5 & 2
  /
 6
   /
  5
   \
4
    /
   3
    \
  2
   \
 1
  \
pi@raspberrypi:/tmp $