BST 包含方法在 JAVA 中无法正常工作

Question

我正在编写一种方法来查看 BST 中是否存在某个值。

 public boolean contains(int val){
        return containsHelper(val, root);
    }
    public boolean containsHelper(int val, Node root){


        if(val < root.val && root.left != null) {
            containsHelper(val, root.left);
        }
        else if(val > root.val && root.right != null) {
            containsHelper(val, root.right);
        }
        else { //theyre equal
            return true;
        }

        return false;

    }

我不明白为什么我的方法不起作用，它进入了它们相等的 else，但仍然返回 false。

Answer 1

考虑添加一个明确的基本案例。以及当您想要 return true 时的明确情况。

public boolean contains(int val){
    return containsHelper(val, root);
}
public boolean containsHelper(int val, Node root){
    if(root == null) return false;

    if(root.val == val) return true;
    else if (root.val < val) {
        return containsHelper(val, root.right);
    }else {
        return containsHelper(val, root.left);
    }
}

Answer 2

这个逻辑不正确：else { //theyre equal不正确。在您的代码中，此 else 块也会在 root.left 或 root.right 为 null 时执行代码应如下所示：

if(val < root.val) {
    if(root.left != null)
        return containsHelper(val, root.left);
    // not going to find val
    else return false;
}
else if(val > root.val) {
    if(root.right != null)
        return containsHelper(val, root.right);
    // not going to find val
    else return false;
}
else { //theyre equal
return true;
}

BST 包含方法在 JAVA 中无法正常工作

BST Contains method not working properly in JAVA

java

recursion

binary-search-tree