Java - 包括 BST

Question

我有这个 BST 问题，我试图用 Java 解决，但我不知道为什么它不起作用。问题是:

• 二叉搜索树 (BST) 是一种二叉树，其中每个值节点大于或等于该节点的所有节点中的值左子树并且小于该树中所有节点的值节点的右子树。

  编写一个函数来检查给定的二叉搜索树是否包含给定值。

  例如，对于下面的树:

  n1(值:1，左:null，右:null)n2(值:2，左:n1，右:n3) n3 (Value: 3, Left: null, Right: null) 调用 contains(n2, 3)应该返回 true，因为根节点为 n2 的树包含数字 3。

这就是我试图解决它的方式:

    class Node {
    public int value;
    public Node left, right;

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

public class BinarySearchTree {
    public static boolean contains(Node root, int value) {
       if(root.value == value)
           return true;

       else if(value < root.value){
           if(root.left == null)
               return false;
           contains(root.left, value);
       }
       else if(value > root.value){
           if(root.right == null)
               return false;
           contains(root.right, value);
       }

        return false;
    }


    public static void main(String[] args) {
        Node n1 = new Node(1, null, null);
        Node n3 = new Node(3, null, null);
        Node n2 = new Node(2, n1, n3);

        System.out.println(contains(n2, 3));
    }
}

这应该返回 true，但它没有...提前谢谢你。

Answer 1

return contains(...) 而不是仅仅为那些递归调用调用 contains(...)，这样您就不会在它们被调用时丢失值制作