二进制搜索树的递归深度

Question

这是作业，不要贴代码。求你了，谢谢你。

我被指派创建一个计算BST中特定的深度的方法。

为此，我需要@Overridea方法公共int深度（T数据）。因此，要递归地找到它，我需要创建一个助手方法。

我知道我需要在树中搜索包含我要查找的数据的节点。为此，我编写了以下代码：

@Override
public int depth(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Data is null");
    }
    if (compare(data, root.getData()) == 0) {
        return 1;
    } else {
        return countNodes(search(root, data), data);
    }
}

private int countNodes(BSTNode<T> node, T data) {
    int depth = 1;
    if (node == null) {
        return 0;
    } else {
        if (compare(data, node.getData()) == 0) {
            return depth;
        } else if (compare(data, node.getData()) < 0) {
            return countNodes(node.getLeft(), data);
        } else {
            return countNodes(node.getRight(), data);
        }
    }
}

private int compare(T a, T b) {
    return a.compareTo(b);
}

然而，这是行不通的，因为每次进行递归调用时，深度将保持1；本质上，它是在重置深度值。我不知道如何在调用之间保持深度的值。

Answer 1

如果当前节点是您正在寻找的节点，您的深度方法应该返回1，或者如果您需要继续寻找，则返回下一个节点的深度加1。

例如：

                        N5
                    N3      N7
                  N1  N4  N6

你想知道N1的深度。

从根开始：

N1！=N5，所以你返回一个加上N3的检查结果。（1（N3检查的结果））

N1！=N3，所以您返回1加上N1的检查结果。（1（1（N1检查结果））

N1==N1所以你你返回一个。（1（1（1）））

(1 (1 (1))) = 3

这是正确的深度，也是初始深度调用将返回的深度。