c++ 查找两个节点的共同祖先的问题

9rygscc1  于 11个月前  发布在  其他
关注(0)|答案(2)|浏览(99)

我有下面的代码,用于在二叉搜索树中查找两个节点的共同祖先。如果代码可以找到第n个共同祖先,则返回共同祖先,如果没有共同祖先,则返回(-1)。逻辑上代码似乎是正确的,但代码开发中有一个错误,我找不到。有任何帮助吗?
我已经添加了二叉搜索树的形象是不显示!!!

vmpqdwk3

vmpqdwk31#

不是一个完整的答案(我相信这是更好的这类问题),这将指出你在正确的方向。
首先,摆脱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));
}


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

vsnjm48y

vsnjm48y2#

比较和条件commonParent->data != n是比较苹果和橘子,即 data 与计数。它们是不相关的。你不能指望commonParent以某种方式走n-1的步骤。这已经太晚了-commonParent是当n为1时的节点,但是对于n的其他值,你需要在树中向上搜索。
我建议首先计算bc的共同祖先节点的数量,然后检查n是否小于或等于b,如果是,再次遍历树以找到相应的节点。
代码:

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;

相关问题