我正在编写一个程序来查找二叉树(不是 BST)中最近的祖先。我找到了一个示例工作代码:
mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;
if(root == NULL)
{
return(NULL);
}
if(root->left==p || root->right==p || root->left==q || root->right==q)
{
return(root);
}
else
{
l = closestAncestor(root->left, p, q);
r = closestAncestor(root->right, p, q);
if(l!=NULL && r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}
我正在尝试做类似下面的事情(只传递数据值并只找到祖先的数据值,而不关心它的指针)
int closestanc(node * root, int n1, int n2)
{
int l, r;
if(root == NULL)
return -1;
if(root->right->data == n1 || root->right->data == n2 || root->left->data == n1 || root->left->data == n2)
return root->data;
else
{
l = closestanc(root->left, n1, n2);
r = closestanc(root->right, n1, n2);
if(l!= -1 && r!= -1)
return root->data;
else
return (l != -1 ? l : r);
}
}
最佳答案
您需要检查 NULL
。变化:
if(root->right->data == n1 || root->right->data == n2 ||
root->left->data == n1 || root->left->data == n2)
到
if ((root->right != NULL && (root->right->data == n1 || root->right->data == n2))
|| (root->left != NULL && (root->left->data == n1 || root->left->data == n2)))
尽管我怀疑您可以用更简单的方式替换它:
if (root->data == n1 || root->data == n2)
不改变函数的输出(尽管它会稍微改变它的工作方式)。
补充说明:
该功能并不太可靠。似乎如果两者都不存在于树中,它仍然会返回一个祖先。为此,我建议返回 -2
(或另一个未使用的值)而不是 root->data;
进行上述检查,这样您就可以确定两者都没有找到。
所以:
if (root->data == n1 || root->data == n2)
return -2;
然后:
- 如果函数返回
-1
,则您知道这两个元素都未找到。 - 如果返回
-2
,则只找到其中一个。 - 如果它返回任何其他东西,那就是最近的祖先。
关于使用数据而不是节点指针的最近祖先函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16986492/