递归二叉搜索树的深度

Question

这是家庭作业，请勿 POST 编码。请谢谢。

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

为此，我要@Override一个方法public int depth(T data)。所以，为了递归地找到它，我需要创建一个辅助方法。

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

@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);
}

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

Answer 1

你的深度方法应该return一个如果当前节点是你正在寻找的那个或者下一个节点的深度加一如果你需要继续寻找。

例如：

                        N5
                    N3      N7
                  N1  N4  N6

你想知道N1的深度

你从根开始：

N1 != N5 所以你 return 一加上你对 N3 的检查结果。 (1 + (N3 检查的结果))

N1 != N3 所以你 return 加上你对 N1 的检查结果。 (1 + (1 + (N1 检查的结果)))

N1 == N1 所以你你return一个。 (1 + (1 + (1)))

(1 + (1 + (1))) = 3

这是正确的深度，也是初始深度调用的深度 return。

递归二叉搜索树的深度

depth of Binary Search Tree recursively

java

recursion

binary-search-tree

depth