我有一棵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;