Поиск, если двоичное дерево является двоичным деревом поиска

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

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

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

Более того, он указывал, что я размышляю над рекурсией. Мой подход 2: BT - это BST, если для любого node N N- > left is < N и N > right > N, а преемник in-order в левом node из N меньше N, а преемник in-order справа node N больше N, а левое и правое поддеревья - BSTs.

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

Ответы

Ответ 1

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

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

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

Ответ 2

Ответ, предоставленный @Dhruv, является хорошим. В дополнение к этому здесь есть еще одно решение, которое работает в O (n) времени.
Мы должны отслеживать предыдущий node в этом подходе. В каждом рекурсивном вызове мы проверяем предыдущие данные node с текущими данными node. Если текущие данные node меньше предыдущего, мы возвращаем 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);
}

Ответ 3

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

Приглашаются комментарии. Спасибо.

Ответ 4

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

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

Ответ 5

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

Более бинарное дерево поиска может иметь объекты, которые сравниваются методом compareTo или Coperator.. (следовательно, Integer.MIN и Integer.MAX не подходят для этой модели) Я пишу код, где он возвращает true или false нужно вызвать (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 ) )

}

Ответ 7

Вот еще одно решение, которое использует 2 вспомогательные функции для вычисления для каждого node минимального и максимального значений в поддереве с помощью вспомогательной функции 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 a BST */
          return(true);
    }