我的C++代码出了什么问题?最不常见的祖先

Question

首先，我对C或C++并不陌生。但是，我目前正在Mac Yosemite上使用C++。我只是尝试编写一个递归函数来返回两个节点的共同祖先，这些祖先由它们的键（数据）变量标识。逻辑很简单，遍历树，直到两个节点在同一个分支中，这些节点分化的节点是共同的祖先。带着这个想法，我想出了以下代码：

Node * commonAncestor(Node *n, int left_elem, int right_elem)
{
    if (n == NULL || n->key()==left_elem || n->key() == right_elem){return NULL;}
    if (left_elem < n->key() && right_elem > n->key()) {return n;}
    if (left_elem > n->key() || right_elem < n->key()) {
        cout<<"n...Consider changing the order of the elements"<<endl;
    }
    if (left_elem < n->key() && right_elem < n->key()) {
        commonAncestor(n->Left(), left_elem, right_elem);
    }
    if (left_elem > n->key() && right_elem > n->key()) {
        commonAncestor(n->Right(), left_elem, right_elem);
    }
}

我

应该工作，我做过类似的程序。但是，程序无法编译。我收到编译器错误"control may reach end of non-void function"这很奇怪，因为我有返回声明。另外，为了避免此错误，我尝试在末尾添加一个 return 语句，该语句仅返回根节点。我很困惑...我应该对XCode设置做点什么吗？我的逻辑错了吗？

Answer 1

这是因为您忘记返回递归调用返回的值。并在末尾添加一个返回NULL，因为编译器不一定知道函数的末尾是无法访问的。

Node * commonAncestor(Node *n, int left_elem, int right_elem)
{
    if (n == NULL || n->key()==left_elem || n->key() == right_elem){return NULL;}
    if (left_elem < n->key() && right_elem > n->key()) {return n;}
    if (left_elem > n->key() || right_elem < n->key()) {
        cout<<"n...Consider changing the order of the elements"<<endl;
        return NULL;
    }
    if (left_elem < n->key() && right_elem < n->key()) {
        return commonAncestor(n->Left(), left_elem, right_elem);
    }
    if (left_elem > n->key() && right_elem > n->key()) {
        return commonAncestor(n->Right(), left_elem, right_elem);
    }
    return NULL;
}

Answer 2

这是因为返回总是在 IF 语句中，所以它们不能被调用......因此，如果它确实进入任何 IF（使用 NULL 或您想要的值），则解决方案也应该在函数末尾调用 return。

Answer 3

编译器不会高兴，除非确定无论如何都会返回某些内容（即使您的 if 处理了所有可能的情况）。最后，你认为你的代码永远不会到达的地方，只要抛出一个return NULL;，它就会很高兴。

另外，我可能是错的，但我相信你也想在最后两个 if 中返回递归调用 commonOriginstor 的结果。