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

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.

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

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

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

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

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

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

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

}

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

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

Вот еще одно решение, которое использует 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);
    }
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);      
}

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

ВАШ ОТВЕТ НА ВОПРОС