java - 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;

    }

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

Answer 1

考虑添加一个明确的基本情况。以及当您想要返回 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);
    }
}