Проверьте, является ли двоичное дерево бинарным деревом поиска. Почему мой код не работает? - PullRequest
Новая
       33

Проверьте, является ли двоичное дерево бинарным деревом поиска. Почему мой код не работает?

0 голосов
/ 14 ноября 2018

Вам задан корень двоичного дерева, и вы должны проверить, является ли оно двоичным деревом поиска. Обратите внимание, что значения всех узлов различны (это вопрос от Hackerrank в разделе Trees). Это ссылка

Я действительно не могу понять, почему мой код не работает. Не имеет смысла.

Вот мой код в Java 

boolean checkBST(Node root) {
    if(root == null) return false; // could be true or false I guess?
    if(root.left == null && root.right == null) return true;

    if(root.left != null && root.right != null) return checkBST(root.left) && checkBST(root.right) && root.left.data < root. data && root.right.data > root.data;

    if(root.left != null) return checkBST(root.left) && root.left.data < root.data;
    if(root.right != null) return checkBST(root.right) && root.right.data > root.data;

    return false;
}

Код выполняется, но в этом тесте он не работает:

2 1 2 4 3 5 6 7

Он выводит yes вместо No. Кроме того, я, к сожалению, не уверен, как они строят деревья из массива, но это не должно иметь значения.

Мои вопросы:

  1. Почему мой код не работает?
  2. Мой первый базовый случай верен? Я установил значение false, чтобы сделать его более сложным
  3. Если есть так много операторов if, и это хороший код или плохой код? Вы рекомендуете использовать операторы if-else?

Спасибо

1 Ответ

0 голосов
/ 14 ноября 2018

Проблема заключается в том, что вы проверяете, что условие выполняется только для непосредственных потомков, а не для всего левого и правого поддеревьев.Вы можете увидеть проблему с вашим кодом визуально в этом примере. 

    3
   / \
  2   5
 / \
1   4

Вы можете видеть, что узел 4 больше, чем его родитель, но не меньше, чем его прародитель.Однако это не должно иметь место, поскольку каждый узел слева от 3 должен быть меньше трех.

Проблема состоит в том, что для каждого узла левые потомки должны быть меньше, чем этот узел, иправые потомки должны быть больше, чем этот узел.Вам нужно отслеживать минимальное и максимальное значение, которое может принять узел. 

boolean checkBST(Node root) {
  return checkBST(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

boolean checkBST(Node root, int min, int max) {
  if(root == null) return true;
  if(root.data < min || root.data > max) return false;

  return checkBST(root.left, min, root.data) && checkBST(root.right, root.data, max);
}

Мы возвращаем true в случае, если root равно null, потому что это легчекстати, когда нам не нужно проверять, что левый и правый узлы не null перед вызовом checkBST на них.Следующее, что вам нужно проверить, это то, что значение root попадает в допустимый диапазон.И последний шаг - убедиться, что все детские ценности также находятся в правильных пределах.Все левые потомки должны быть меньше корня, а правые потомки должны быть больше корня.Таким образом, для проверки левых потомков мы делаем значение корня максимальным, а для правых потомков мы делаем значение корня минимальным.

...