在二叉搜索树中查找数据点的深度

Question

这是家庭作业。不要只发布代码。

我需要在二进制搜索树中找到给定数据点的深度。我实现了一个＜code＞depth（）＜/code＞方法和一个helper方法＜code＞countNodes（）＜/code＞，它递归地对节点进行计数。

如果我们要搜索的数据不在树中，我需要返回< code>-1。根据我的递归，我看不出这怎么可能。

@Override
public int depth(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Data is null");
    }
    //FIXME don't use the contains() method
    return countNodes(root, data);
}

/**
 * Helper method counts teh nodes
 * @param  node the node we're going to start counting at
 * @param  data that we're looking for
 * @return the sum of the number of children nodes
 */
private int countNodes(BSTNode<T> node, T data) {
    if (node == null) {
        return 0;
    }
    if (compare(data, node.getData()) == 0) {
        return 1;
    } else if (compare(data, node.getData()) < 0) {
        return 1 + countNodes(node.getLeft(), data);
    } else if (compare(data, node.getData()) > 0) {
        return 1 + countNodes(node.getRight(), data);
    } else {
        return -1;
    }
}

Answer 1

在这种情况下，一般的想法是将“未找到”状态（在本例中为-1）带到递归树中。您可以通过检查递归调用是否返回了-1-如果是，则返回-1直到调用堆栈的顶部，如果不是，则继续正常操作。