为两个节点查找共同祖先时出现问题

比较和条件是将苹果与橙子进行比较，即带有计数的数据。它们是无关的。你不能指望以某种方式向上走几步。现在已经太晚了 -- 是 when 为 1 的节点，但对于其他值，您需要向上爬。commonParent->data != ncommonParentn-1commonParentnn

我建议首先计算 和 的共同祖先的节点数，然后检查是否小于或等于该节点，如果是，则再次遍历树以找到相应的节点。bcn

法典：

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;

不是一个完整的答案（我相信这类问题更好），这将为你指明正确的方向。

首先，去掉 C 风格的原始指针和数组，将你的 Node 结构改为

struct Node {
    int data;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

因为您的树对节点的唯一所有权进行了建模。然后将您的树构建器签名更改为：

std::unique_ptr<Node> buildBST(std::vector<int> values) {
    if (values.empty()) return nullptr;
    auto root = std::make_unique<Node>(values.front());
    for (int i = 1; i < values.size(); ++i) {
        int val       = values[i];
        Node* current = root.get();
        while (true) {
/* etc etc ... the rest of your builder code */
}

然后，您正在寻找 2 个节点的第 n 个父节点，然后为您的查找函数提供所需的祖先级别，最好是这样的方式：

// or return Node* if you prefer
int findCommonParent(Node* root, int val1, int val2, int levelOfAncestry) {
/* body ... */
/* HINT: record the path while you are traversing the tree */
}

最后，为你的代码编写单元测试（googletest 在这方面对初学者非常友好）：

TEST(xxx, yyy) {
    std::vector<int> values({25, 20, 36, 10, 22, 30, 40, 5, 12, 28, 38, 48});
    int valA = 5;
    int valB = 12;
    int expectedResult1 = 10;
    int expectedResult2 = 20;
    auto root = buildBST(values);
    ASSERT_EQ(expectedResult1, findCommonParent(root.get(), valA, valB, 1));
    ASSERT_EQ(expectedResult2, findCommonParent(root.get(), valA, valB, 2));
}

你最终会得到一个清晰的代码，一切都会变得更容易。