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

33

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.

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

Он хотел, чтобы я оптимизировал это с точки зрения времени. Я думаю, что это не может быть сделано менее чем за O (n) dharam
Вот Это Да! это правда, мне, вероятно, не нужен массив, даже тогда порядок O (n) dharam
Можете ли вы определить, что ваш интервьюер имел в виду под "эффективным"? Он имел в виду время или пространство? Я склонен согласиться с вами, что вы не можете сделать это без проверки каждого узла, но вам не нужен массив. shambulator
Он хочет, чтобы вы сказали ему, что этоcannot be done менее чем за O (n) :-), и если кто-то заявляет, что может, можно заменить один из узлов, который не был проверен разрушающим BST-значением, чтобы показать, что он не прав. (Не забывайте, что честно спрашивать невозможное в интервью;) Frank
Обход по порядку уже дает вам значения в порядке их появления в массиве, поэтому вам не нужно копировать все дерево, вам просто нужно отслеживать последнее найденное значение, чтобы его можно было сравнить с текущим один. shambulator

Ваш Ответ

7   ответов
78

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

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), поскольку каждый узел проверяется один раз.

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

выражение внутри вашего оператора if является логическим. просто верни это.
Что ваш код делает с таким деревомdropbox.com/s/mg7jpqbn9z7jvn1/… , Разве это не соответствует истине? (Даже если это не BST)
Я просто не получаю эту строку Math.min (node.value, MAX), не могли бы вы дать более подробное объяснение?
Этот алгоритм не работает правильно для всех входных значений. Например, если корневой узел имеет значение Integer.MIN_VALUE или Integer.MAX_VALUE, алгоритм вернет false, но на самом деле это будет идеальный BST и должен вернуть true. Чтобы исправить алгоритм, вы можете заменить начальные минимальные, максимальные значения на нулевые и проверить на обнуляемость. Таким образом, ваш алгоритм будет работать для всех входных значений.
Я думаю, что Math.min (node.value, MAX) можно просто заменить на node.value
7

Ответ @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);
}

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

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

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

Лучше всего повторить важные части ссылок внутри самой SO, поскольку ссылки могут не сохраняться со временем или содержать постороннюю информацию.
Пожалуйста, не вставляйте ссылки
-1

Есть несколько примеров выше с использованием 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 ) )

}
Значения MIN и MAX связывают проверку на нижних уровнях дерева со значениями предков. Ваша функция не знает значений своих предков и поэтому может неправильно помечать деревья как допустимые.
MIN и MAX просто для того, чтобы избежать углового случая и сделать этот рекурсивный вызов симметричным. dharam
да я понял .. почему это так ..
0

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

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

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

Вот еще одно решение, которое использует 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);
    }
Разве это не пересекает дерево дважды?
1
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);      
}

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

Похожие вопросы