Поиск, является ли Бинарное дерево бинарным деревом поиска [дубликат]

This question already has an answer here:

How do you validate a binary search tree? 30 answers

Сегодня у меня было интервью, где меня попросили написать программу, которая принимает двоичное дерево и возвращает значение true, если оно также является двоичным деревом поиска, в противном случае - false.

Мой подход 1: выполнить обход в порядке и сохранить элементы в O (n) времени. Теперь просмотрите массив / список элементов и проверьте, есть ли элемент в ith индекс больше, чем элемент в (i + 1)th индекс. Если такое условие встречается, вернуть false и выйти из цикла. (Это занимает O (N) время). В конце верните истину.

Но этот господин хотел, чтобы я дал эффективное решение. Я пытался, но безуспешно, потому что, чтобы определить, является ли это BST, я должен проверить каждый узел.

Более того, он указывал мне подумать над рекурсией. Мой подход 2: BT - это BST, если для любого узла N N -> слева - & lt; N и N-> справа & gt; N, и правопреемник правого узла N меньше, чем N, и правопреемник правого узла N больше N, а левое и правое поддеревья являются BST.

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

 shambulator31 мая 2012 г., 13:31
Обход по порядку уже дает вам значения в порядке их появления в массиве, поэтому вам не нужно копировать все дерево, вам просто нужно отслеживать последнее найденное значение, чтобы его можно было сравнить с текущим один.
 dharam31 мая 2012 г., 13:42
Он хотел, чтобы я оптимизировал это с точки зрения времени. Я думаю, что это не может быть сделано менее чем за O (n)
 dharam31 мая 2012 г., 13:35
Вот Это Да! это правда, мне, вероятно, не нужен массив, даже тогда порядок O (n)
 Frank31 мая 2012 г., 14:15
Он хочет, чтобы вы сказали ему, что этоcannot be done менее чем за O (n) :-), и если кто-то заявляет, что может, можно заменить один из узлов, который не был проверен разрушающим BST-значением, чтобы показать, что он не прав. (Не забывайте, что честно спрашивать невозможное в интервью;)
 shambulator31 мая 2012 г., 13:38
Можете ли вы определить, что ваш интервьюер имел в виду под "эффективным"? Он имел в виду время или пространство? Я склонен согласиться с вами, что вы не можете сделать это без проверки каждого узла, но вам не нужен массив.

Ответы на вопрос(7)

Решение Вопроса

Это довольно известная проблема со следующим ответом:

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
     if(node == null)
         return true;
     return node.value > l 
         && node.value < h
         && isValidBST(node.left, l, node.value)
         && isValidBST(node.right, node.value, h);
}

Рекурсивный вызов гарантирует, что узлы поддерева находятся в пределах диапазона своих предков, что важно. Сложность времени выполнения будет O (n), поскольку каждый узел проверяется один раз.

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

 13 нояб. 2015 г., 19:07
Я просто не получаю эту строку Math.min (node.value, MAX), не могли бы вы дать более подробное объяснение?
 14 дек. 2015 г., 12:14
Этот алгоритм не работает правильно для всех входных значений. Например, если корневой узел имеет значение Integer.MIN_VALUE или Integer.MAX_VALUE, алгоритм вернет false, но на самом деле это будет идеальный BST и должен вернуть true. Чтобы исправить алгоритм, вы можете заменить начальные минимальные, максимальные значения на нулевые и проверить на обнуляемость. Таким образом, ваш алгоритм будет работать для всех входных значений.
 17 нояб. 2015 г., 22:28
Я думаю, что Math.min (node.value, MAX) можно просто заменить на node.value
 17 июл. 2014 г., 02:42
Что ваш код делает с таким деревомdropbox.com/s/mg7jpqbn9z7jvn1/… , Разве это не соответствует истине? (Даже если это не BST)
 24 июл. 2017 г., 22:25
выражение внутри вашего оператора if является логическим. просто верни это.

Ответ @Dhruv хороший. В дополнение к этому здесь есть еще одно решение, которое работает за время O (n).
Нам нужно отслеживать предыдущий узел в этом подходе. В каждом рекурсивном вызове мы проверяем данные предыдущего узла с данными текущего узла. Если данные текущего узла меньше предыдущих, мы возвращаем false

int isBST(node* root) {
  static node* prev  = NULL;

  if(root==NULL)
    return 1;

  if(!isBST(root->left))
    return 0;

  if(prev!=NULL && root->data<=prev->data)
    return 0;

  prev = root;
  return isBST(root->right);
}

 06 июн. 2014 г., 10:28
@ NoobEditor Я так не думаю. Поскольку он сканирует узлы по порядку, если какой-либо левый потомок больше, чем его родитель, он вернет 0 в этот момент. Таким образом, если 2-й левый потомок больше, чем родительский узел, чем 1-й левый потомок родителя также был бы больше, чем он, в противном случае функция вернула бы значение 0. Если вы можете вспомнить какой-то случай, когда функция не работает, сообщите об этом.
 05 июн. 2014 г., 09:17
prev!=NULL && root->data<=prev->data ... неверно .... если 2-й левый ребенок больше, чем родитель, этот алгоритм потерпит неудачу в этом случае!
 06 июн. 2014 г., 11:24
Вы кодируете только проверки для непосредственных потомков ... а не дочерних элементов. В качестве первого обхода ширины, возьмите этот сценарий[10 8 15 5 12]
 21 июн. 2014 г., 13:14
Я попытался сделать это с root = 10, root-> left = 8, root-> right = 15, root-> left-> left = 5, root-> left-> right = 12, и это работает правильно!

Посмотрите на это решение: http://preparefortechinterview.blogspot.com/2013/09/am-i-bst.html

Он объясняет разные способы и дает вам общий и эффективный метод тоже. Надеюсь, поможет.

 02 окт. 2015 г., 14:33
Пожалуйста, не вставляйте ссылки
 28 мая 2014 г., 16:09
Лучше всего повторить важные части ссылок внутри самой SO, поскольку ссылки могут не сохраняться со временем или содержать постороннюю информацию.

Есть несколько примеров выше с использованием INTEGER.MAX AND MIN Я не вижу причин, чтобы передать их и значение этого, поправьте меня, если я ошибаюсь, или объясните мне причину.

Более того, в бинарном дереве поиска могут быть объекты, которые сравниваются методом CompareTo или Coperator .. (следовательно, Integer.MIN и Integer.MAX не подходят для этой модели) Я пишу код, где он возвращает истину или ложь нужно вызвать (root_node, true) и он вернет true, если это bst else false

void boolean isBSt( node root_node, boolean passed_root)
{

  if ( node==null){
        if ( passed_root)
        return false;
        // you have passed null pointer as 
        //root of the tree , since there is no 
        // valid start point we can throw an exception or return false      
        return true;
   }

  if( node.right !=null ) 
     if ( node.right.data <= node.data)
   return false;

  if ( node.left !=null ) 
        if ! ( node.left.data <= node.data) 
    return false;

  return ( isBST( node.right , false) && isBST( node.left, false ) )

}
 22 мая 2013 г., 09:40
да я понял .. почему это так ..
 dharam21 мая 2013 г., 10:59
MIN и MAX просто для того, чтобы избежать углового случая и сделать этот рекурсивный вызов симметричным.
 28 мая 2014 г., 16:05
Значения MIN и MAX связывают проверку на нижних уровнях дерева со значениями предков. Ваша функция не знает значений своих предков и поэтому может неправильно помечать деревья как допустимые.

Я думаю, что второй подход правильный. Дерево может быть пройдено рекурсивным способом. На каждой итерации могут быть сохранены нижняя и верхняя границы текущего поддерева. Если мы хотим проверить поддерево с корнем x, а границы для поддерева - это l и h, то все, что нам нужно, это проверить, что l & lt; = x & lt; = h, и проверить левое поддерево с границами l и x, и правильный с оценками х и ч.

Это будет иметь сложность O (n), потому что мы начинаем с корня, и каждый узел проверяется только один раз как корень некоторого поддерева. Также нам понадобится O (h) памяти для рекурсивных вызовов, где h - высота дерева.

 dharam31 мая 2012 г., 13:27
Можете ли вы уточнить и объяснить сложность времени выполнения этого подхода. По мне его больше, чем O (n). Но я не уверен.
 dharam31 мая 2012 г., 13:37
Итак, по вашему мнению, это все равно будет принимать O (n). Меня попросили оптимизировать это.

Вот еще одно решение, которое использует 2 вспомогательные функции для вычисления для каждого узла минимального и максимального значения в поддереве с использованием вспомогательных функций minValue и maxValue.

int isBST(struct node* node)
    {
      if (node == NULL)
        return(true); 

      /* false if the max of the left is > than us */
        if (node->left!=NULL && maxValue(node->left) > node->data)
            return(false); 

      /* false if the min of the right is <= than us */
        if (node->right!=NULL && minValue(node->right) < node->data)
            return(false); 

      /* false if, recursively, the left or right is not a BST */ 
         if (!isBST(node->left) || !isBST(node->right))
           return(false); 

      /* passing all that, it's a BST */
          return(true);
    }
 10 июн. 2012 г., 07:49
Разве это не пересекает дерево дважды?
boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max){
  if(node == null){
    return true;
  }

  boolean left  = isBinarySearchTree(node.getLeft(), min, node.getValue());
  boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

  return left && right && (node.getValue()<max) && (node.getValue()>=min);      
}

Комментарии приветствуются. Благодарю.

Ваш ответ на вопрос