Как написать функцию, которая проверяет, содержит ли данное двоичное дерево поиска заданное значение?

Question

Например, для следующего дерева:

n1 (значение: 1, слева: ноль, справа: ноль) n2 (значение: 2, слева: n1, справа: n3) n3 (значение: 3, слева: ноль, справа: ноль) Вызов содержимого (n2, 3) должен возвращать значение true, поскольку дерево с корнем в n2 содержит число 3.

Я новичок в программировании и пытаюсь решить задачу, чтобы понять концепции программирования. Это не домашнее задание.

Я написал код ниже, но он всегда возвращает false.

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 BinaryTree {

   public static boolean contains(Node root, int value){
        if(root == null) return false;
        else
            return
                    contains(root.left, value) ||
                    contains(root.right, value);
    }

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

Answer 1

Вы пропускаете проверку, если значение в узле соответствует значению, которое вы ищете. Таким образом, вы в основном всегда возвращаете false, потому что в одной точке корень будет равен нулю. Чтобы избежать этого, вам нужно предложение else if, где вы проверяете значение узла и ищете значение и возвращаете true, если эти два значения равны.

public static boolean contains(Node root, int value){
    if(root == null) return false;
    else if (root.value==value) return true;
    else
        return
                contains(root.left, value) ||contains(root.right, value);
}