我有一棵BST树。我想创建一个获取值并返回包含其值的节点的级别的方法(根= 0),没有这样的节点吗?返回-1。
我想递归地做。
这段代码可以正常工作:

    private int recursiveContains(BinaryNode node, int searchVal){
    int nodeKey = node.nodeKey;
    if (searchVal < nodeKey){
        if (node.leftChild != EMPTY_NODE)
            return 1 + recursiveContains(node.leftChild, searchVal);
    }else if (searchVal > nodeKey){
        if (node.rightChild != EMPTY_NODE)
            return 1 + recursiveContains(node.rightChild, searchVal);
    }
    return 0;
}


但是,只要树包含搜索值即可。

当我到达叶子并没有找到值时,如何停止迭代并返回-1?
是否可能递归?

谢谢

最佳答案

您只需要调整您的最终情况。现在,如果该值不在树中,则只返回要插入该值的节点的深度,因为最后一种情况就是return 0。相反,您需要显式检查当前节点是否确实是正确的节点。如果是,则可以返回0;否则,您应该返回-1。然后,递归调用需要查找该特殊值并进行适当处理。

我可能会在一开始就进行此显式检查-这是请求的节点的基本情况。然后最后,您的“ fall-through”值(如果没有其他条件为真时返回的值)为-1。因此,您将得到如下所示的结果:

// WARNING: UNTESTED CODE
if (searchVal == nodeKey) {
    return 0;
} else if (searchVal < nodeKey && node.leftChild != EMPTY_NODE) {
    int childResult = recursiveContains(node.leftChild, searchVal);
    if (childResult != -1) { // Only use the child result if the value was found.
        return 1 + childResult;
    }
} else if (searchVal > nodeKey && node.rightChild != EMPTY_NODE) {
    int childResult = recursiveContains(node.rightChild, searchVal);
    if (childResult != -1) { // Only use the child result if the value was found.
        return 1 + childResult;
    }
}
// If you haven't returned by now, the value can't be found along this path.
return -1;

10-02 03:47
查看更多