寻找两个节点的共同祖先的问题

Question

我有以下代码用于查找二叉搜索树中两个节点的第 n 个共同祖先。如果代码可以找到第 n 个共同祖先，则将返回共同祖先，如果没有共同祖先，则将返回 (-1)。从逻辑上讲，代码似乎是正确的，但代码开发中有一个错误，我找不到该错误。有没有机构可以帮忙？

代码输入：

第一输入行：节点数，例如：12

第二输入行：按级别顺序遍历的节点，例如：25 20 36 10 22 30 40 5 12 28 38 48

第三输入行：两个节点找到它们的第 n 个共同祖先，例如： : 5 12

第四输入行：查找的第 n 个共同祖先，例如：1

代码输出： 找到的第 n 个共同祖先：例如：10

                     25
            20                 36
       10       22         30       40
     5    12            28        38   48

对于上述示例，代码为第一个、第二个和第三个共同祖先返回 10，这是不正确的。

我添加了不显示的二叉搜索树图像！！！

 #include <iostream>
 using namespace std;

 struct Node {
 int data;
 Node* left;
 Node* right;

 Node(int val) : data(val), left(nullptr), right(nullptr) {}
 };

 Node* buildBST(int levelOrder[], int a) {
    if (a == 0)
    return nullptr;

   Node* root = new Node(levelOrder[0]);

  for (int i = 1; i < a; ++i) {
    int val = levelOrder[i];
    Node* current = root;

    while (true) {
        if (val < current->data) {
            if (current->left == nullptr) {
                current->left = new Node(val);
                break;
            } else {
                current = current->left;
            }
        } else {
            if (current->right == nullptr) {
                current->right = new Node(val);
                break;
            } else {
                current = current->right;
            }
        }
    }
  }

  return root;
}

 Node* findCommonParent(Node* root, int c, int b) {
  while (root != nullptr) {
    if (root->data > c && root->data > b) {
        root = root->left;
    } else if (root->data < c && root->data < b) {
        root = root->right;
    } else {
        return root;
    }
 }
 return nullptr;
}

 int main() {
  int a;
  cin >> a;

 int levelOrder[100]; 
 for (int i = 0; i < a; ++i) {
    cin >> levelOrder[i];
 }

 int c, b;
 cin >> c >> b;

 int n;
 cin >> n;

 Node* root = buildBST(levelOrder, a);

 Node* commonParent = findCommonParent(root, c, b);

 if (commonParent != nullptr && commonParent->data != n) {
     cout << commonParent->data << endl;
 } else {
    cout << "-1" << endl;
 }

 return 0;
 }

Answer 1

比较和条件

commonParent->data != n

是将苹果与橙子进行比较，即数据与计数。他们是不相关的。你不能指望

commonParent

能以某种方式向上走

n-1

步。现在已经太晚了 -

commonParent

是

n

为 1 时的节点，但对于

n

的其他值，您需要在树上up。

我建议首先计算

b

和

c

的共同祖先节点的数量，然后检查

n

是否小于或等于该数，如果是，则再次遍历树以找到对应的节点。

代码：

int countCommonAncestors(Node* root, int c, int b) {
    int count = 0;
    while (root != nullptr) {
        count++;
        if (root->data > c && root->data > b) {
            root = root->left;
        } else if (root->data < c && root->data < b) {
            root = root->right;
        } else {
            break;
        }
    }
    return count;
}

int getDataOnPath(Node* root, int b, int level) {
    while (level-- > 0) {
        root = root->data > b ? root->left : root->right;
    }
    return root->data;
}

在您的

main

中，您可以执行以下操作：

    int count = countCommonAncestors(root, c, b);
    int result = count < n ? -1 : getDataOnPath(root, b, count - n);
    cout << result << endl;