Java BST递归变量设置

Question

我有一个普通的二叉搜索树，它使用数据的字符串值以及左右节点来实现。该树工作正常，但我的rankOf 函数遇到问题。我使用递归来查找节点，并且当元素存在时该方法是成功的，但是当不存在值时则不起作用，并且我无法弄清楚如何在其中设置 boolean 值来帮助解决此问题。这是代码:

private int rankOf(String s, Node n){
    if (n != null){

        //check root
        if (s.compareTo(n.value) == 0){
            if (n.left != null){
                return size(n.left);
            }
            return 0;
        }
        // only worry about left tree, easy
        if (s.compareTo(n.value) < 0){
            return rankOf(s, n.left);
        } else {
            // must count entire left tree plus root node
            return rankOf(s, n.right) + size(n.left) + 1;
        }

    }
    //null or not found
    return 0;
}

当 root 等于值时，我知道该元素在树中，因此应该有一些东西进入其中，但不确定如何处理这个问题。

Answer 1

这个检查是没有用的:

if (n.left != null){
     return size(n.left);
}

无论如何，你可以这样做:

static int rankOf(String s, Node root) {
    if(root == null) {
        return -1;
    }

    if(root.value.equals(s)) {
        return size(root);
    }

    int result;
    if(s.compareTo(root.value) > 0) {
        result = rankOf(s, root.right);
    } else {
        result = rankOf(s, root.left);
    }
    return result;
}

还有你的size()方法:

static int size(Node root) {
    if(root == null) return 0;
    return size(root.left) + size(root.right) + 1;
}

如果未找到String，将返回-1。