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));
}
比较和条件commonParent->data != n是比较苹果和橘子,即 data 与计数。它们是不相关的。你不能指望commonParent以某种方式走n-1的步骤。这已经太晚了-commonParent是当n为1时的节点,但是对于n的其他值,你需要在树中向上搜索。 我建议首先计算b和c的共同祖先节点的数量,然后检查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;
2条答案
按热度按时间vmpqdwk31#
不是一个完整的答案(我相信这是更好的这类问题),这将指出你在正确的方向。
首先,摆脱C风格的原始指针和数组,将Node结构改为
字符串
因为你的树对节点的唯一所有权进行了建模。然后将你的树构建器签名更改为:
型
然后,您正在查找2个节点的第n个父节点,然后向查找函数提供所需的祖先级别,最好是这样:
型
最后,为你的代码编写单元测试(googletest在这方面对初学者非常友好):
型
你会得到一个清晰的代码,一切都会变得更容易。
vsnjm48y2#
比较和条件
commonParent->data != n
是比较苹果和橘子,即 data 与计数。它们是不相关的。你不能指望commonParent
以某种方式走n-1
的步骤。这已经太晚了-commonParent
是当n
为1时的节点,但是对于n
的其他值,你需要在树中向上搜索。我建议首先计算
b
和c
的共同祖先节点的数量,然后检查n
是否小于或等于b
,如果是,再次遍历树以找到相应的节点。代码:
字符串
在
main
中,您可以执行以下操作:型