Sprawdź poprawność drzewa wyszukiwania binarnego

Poziom trudności Średni
Często zadawane pytania Amazonka Apple Asana Atlassian Bloomberg ByteDance Cytadela Facebook Microsoft wyrocznia Qualtrics VMware Yahoo
Głębokie pierwsze wyszukiwanie Rekurencja Drzewoodwiedzajacy 70

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem

In Sprawdź poprawność drzewa wyszukiwania binarnego problem podaliśmy korzeń a drzewo, musimy sprawdzić, czy jest to drzewo wyszukiwania binarnego, czy nie.

Przykład:

Sprawdź poprawność drzewa wyszukiwania binarnegoszpilka

Wyjście:

prawdziwy

Wyjaśnienie: Podane drzewo jest binarnym drzewem wyszukiwania, ponieważ wszystkie elementy pozostawione w każdym poddrzewie są mniejsze niż korzeń poddrzewa. Wszystkie elementy, które mają prawo do każdego poddrzewa, są większe niż katalog główny poddrzewa, a każde poddrzewo samo w sobie jest binarnym drzewem wyszukiwania.

Podejście

  • Po pierwsze, robimy w porządku przejście danego drzewa i przechowuj je w pliku szyk. Następnie sprawdzamy, czy tablica jest posortowana w kolejności rosnącej. Następnie mówimy, że jest to drzewo wyszukiwania binarnego, w przeciwnym razie nie jest drzewem wyszukiwania binarnego.
  • Aby zminimalizować wykorzystanie przestrzeni pomocniczej, możemy śledzić poprzednio odwiedzany węzeł i jeśli bieżący węzeł jest mniejszy niż poprzedni, to nie jest drzewo wyszukiwania binarnego a jeśli wszystkie poprzednie węzły są mniejsze niż węzeł bieżący, to jest to drzewo wyszukiwania binarnego.
  • Możemy uniknąć użycia dodatkowej przestrzeni, przekazując poprzedni węzeł jako parametr.

Kod C ++ dla walidacji drzewa wyszukiwania binarnego

// C++ program to check if a given tree is BST. 
#include <bits/stdc++.h> 
using namespace std; 

/* A binary tree node has data, pointer to 
left child and a pointer to right child */
struct Node 
{ 
  int data; 
  struct Node* left, *right; 
  
  Node(int data) 
  { 
    this->data = data; 
    left = right = NULL; 
  } 
}; 


bool isBSTUtil(struct Node* root, Node *&prev) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root) 
  { 
    if (!isBSTUtil(root->left, prev)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != NULL && root->data <= prev->data) 
    return false; 

    prev = root; 

    return isBSTUtil(root->right, prev); 
  } 

  return true; 
} 

bool isBST(Node *root) 
{ 
   Node *prev = NULL; 
   return isBSTUtil(root, prev); 
} 

/* Driver program to test above functions*/
int main() 
{ 
  struct Node *root = new Node(3); 
  root->left	 = new Node(2); 
  root->right	 = new Node(5); 
  root->left->left = new Node(1); 
  root->left->right = new Node(4); 

  if (isBST(root)) 
    cout << "Is BST"; 
  else
    cout << "Not a BST"; 

  return 0; 
} 

Kod Java do walidacji drzewa wyszukiwania binarnego

// Java program to check if a given tree is BST. 
class Check
{ 
/* A binary tree node has data, pointer to 
left child and a pointer to right child */
static class Node 
{ 
  int data; 
  Node left, right; 
  
  Node(int data) 
  { 
    this.data = data; 
    left = right = null; 
  } 
}; 
static Node prev; 

static boolean isBSTUtil(Node root) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root != null) 
  { 
    if (!isBSTUtil(root.left)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != null && root.data <= prev.data) 
    return false; 

    prev = root; 

    return isBSTUtil(root.right); 
  } 
  return true; 
} 

static boolean isBST(Node root) 
{ 
  return isBSTUtil(root); 
} 

// Driver Code 
public static void main(String[] args) 
{ 
  Node root = new Node(3); 
  root.left	 = new Node(2); 
  root.right	 = new Node(5); 
  root.left.left = new Node(1); 
  root.left.right = new Node(4); 

  if (isBST(root)) 
    System.out.print("Is BST"); 
  else
    System.out.print("Not a BST"); 
} 
} 
Not a BST

Złożoność czasowa

Na) ponieważ przechodzimy przez każdy węzeł tylko raz.

Złożoność przestrzeni

Na) ponieważ przechowujemy każdy przemierzany węzeł i sprawdzamy, czy tablica jest posortowana w kolejności rosnącej, aby sprawdzić, czy drzewo jest drzewem wyszukiwania binarnego, czy nie.

Referencje

Wywiady dotyczące projektowania systemu pękania
Translate »