Ελέγξτε εάν κάθε εσωτερικός κόμβος ενός BST έχει ακριβώς ένα παιδί


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Accenture αμαζόνα Μονοτυπικές Λύσεις PayPal Synopsys
Δυαδικό δέντρο αναζήτησης Δυαδικό δέντρο Δέντρο

Δήλωση προβλήματος

"Ελέγξτε εάν κάθε εσωτερικός κόμβος ενός BST έχει ακριβώς ένα παιδί", αναφέρει ότι σας δίνεται μια προπαραγγελία διέλευσης ενός δέντρου δυαδικής αναζήτησης. Και πρέπει να βρείτε εάν όλοι οι κόμβοι χωρίς φύλλα περιέχουν μόνο ένα παιδί. Εδώ θεωρούμε επίσης ότι όλοι οι κόμβοι στη δεδομένη είσοδο έχουν ξεχωριστές τιμές.

Παράδειγμα

Ελέγξτε εάν κάθε εσωτερικός κόμβος ενός BST έχει ακριβώς ένα παιδί

 

Preorder Traversal: 6 15 7 9 11
Yes

Επεξήγηση: Όπως μπορούμε να δούμε στην παραπάνω εικόνα, το δέντρο με τη δεδομένη προπαραγγελία διέλευσης έχει ένα μόνο παιδί για κάθε εσωτερικό κόμβο. Έτσι, η έξοδος είναι ναι.

Προσέγγιση για να ελέγξετε εάν κάθε εσωτερικός κόμβος ενός BST έχει ακριβώς ένα παιδί

Προπαραγγελία διέλευσης σημαίνει ότι η ρίζα έχει προτεραιότητα και εκτυπώνεται πριν από το αριστερό και το δεξί υπόφυτο. Έτσι, τα στοιχεία μετά τη ρίζα είναι είτε μικρότερα είτε μεγαλύτερα από τη ρίζα. Έτσι, εάν πρέπει να ελέγξουμε εάν μια δεδομένη ακολουθία είναι προπαραγγελία του a Δυαδικό δέντρο αναζήτησης. Μπορούμε να χρησιμοποιήσουμε δύο ένθετους βρόχους για να ελέγξουμε εάν μπορούμε να δημιουργήσουμε ένα δέντρο δυαδικής αναζήτησης με τη δεδομένη ακολουθία.

Naive προσέγγιση

Όπως ήδη συζητήσαμε, αυτή η προπαραγγελία διέλευση περιέχει τη ρίζα στην κορυφή και μετά την εκτύπωση του αριστερού και του δεξιού υποδέντρου. Τώρα αυτή η λειτουργία έχει ολοκληρωθεί αναδρομικά έως ότου καλυφθούν όλοι οι κόμβοι στο δέντρο. Έτσι, μπορούμε να ελέγξουμε εάν η δεδομένη ακολουθία αντιπροσωπεύει ένα BST, εκτελούμε δύο ένθετους βρόχους όπου ο εξωτερικός βρόχος χρησιμοποιείται για να επιλέξει μια ρίζα. Και ο ένθετος βρόχος ελέγχει εάν τα στοιχεία μετά από αυτό μπορούν να αντιπροσωπεύσουν το αριστερό και το δεξιό του υπόφυτο. Για αυτό, ελέγχουμε εάν μέχρι ένα συγκεκριμένο ευρετήριο όλα τα στοιχεία είναι μικρότερα από το επιλεγμένο στοιχείο. Και τα στοιχεία μετά είναι μεγαλύτερα από το επιλεγμένο στοιχείο. Τώρα, μπορούμε να τροποποιήσουμε αυτήν την προσέγγιση σύμφωνα με την περίπτωση χρήσης μας.

Ας δούμε πώς μπορούμε να τροποποιήσουμε τον αλγόριθμο για να ελέγξουμε εάν κάθε εσωτερικός κόμβος ενός BST έχει ακριβώς ένα παιδί. Εάν το εσωτερικό παιδί του BST έχει ακριβώς ένα παιδί. Αυτό σημαίνει ότι κάθε εσωτερικός κόμβος μπορεί να έχει είτε αριστερό υποδένδρο είτε δεξιό υποδένδρο. Δεν θα περιέχει και τα δύο δευτερεύοντα δέντρα ταυτόχρονα. Έτσι, για να συνοψίσουμε τον αλγόριθμό μας. Χρησιμοποιούμε δύο ένθετους βρόχους, όπου ο εξωτερικός βρόχος επιλέγει ένα στοιχείο. Στη συνέχεια, ο ένθετος βρόχος χρησιμοποιείται για να ελέγξει εάν στοιχεία που έρχονται μετά ανήκουν σε οποιονδήποτε από τα δευτερεύοντα δέντρα. Στο παρελθόν, είχαμε ένα συγκεκριμένο ευρετήριο πριν από το οποίο τα στοιχεία ήταν μικρότερα από τη ρίζα, μετά τα οποία τα στοιχεία ήταν μεγαλύτερα από αυτό. Τώρα, δεν θα βρούμε τέτοιο ευρετήριο. Αλλά αυτή η μέθοδος δεν είναι αρκετά αποτελεσματική, επειδή έχει πολυπλοκότητα χρόνου πολυπλοκότητας του O (N ^ 2).

Αποτελεσματική προσέγγιση

Μέχρι τώρα, έχουμε ξεκαθαρίσει ένα σημείο ότι όλα τα παιδιά κάθε κόμβου θα είναι είτε μικρότερα ή μεγαλύτερα από τον τρέχοντα κόμβο σύμφωνα με αυτό το πρόβλημα. Έτσι, για να ελέγξετε εάν κάθε εσωτερικός κόμβος ενός BST έχει ακριβώς ένα θυγατρικό, βρίσκουμε τον επόμενο προγενέστερο διάδοχο του τρέχοντος κόμβου. Στη συνέχεια, βρίσκουμε τον τελευταίο διάδοχο προπαραγγελίας του τρέχοντος κόμβου. Εάν και οι δύο διάδοχοι είναι μικρότεροι από τον τρέχοντα κόμβο ή μεγαλύτερος από τον τρέχοντα κόμβο. Στη συνέχεια προχωράμε αλλιώς γνωρίζουμε ότι ο τρέχων κόμβος έχει και αριστερό και δεξιό υπόφυτο επειδή ένα από τα στοιχεία είναι μικρότερο από τον τρέχοντα κόμβο. Και ένας άλλος κόμβος είναι μεγαλύτερος από τον τρέχοντα κόμβο. Έτσι επιστρέφουμε ψευδείς ή -1 σύμφωνα με τις απαιτήσεις μας.

Κώδικας

Κωδικός C ++ για να ελέγξετε εάν κάθε εσωτερικός κόμβος ενός BST έχει ακριβώς ένα παιδί

#include<bits/stdc++.h>
using namespace std;

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

Κωδικός Java για να ελέγξετε εάν κάθε εσωτερικός κόμβος ενός BST έχει ακριβώς ένα θυγατρικό

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας

O (N), αφού μόλις περάσαμε από τον πίνακα προπαραγγελίας. Και ο πίνακας προπαραγγελίας έχει στοιχεία N, έτσι μια γραμμική πολυπλοκότητα χρόνου.

Διαστημική πολυπλοκότητα

O (N), ο χώρος που απαιτείται για την αναδρομική στοίβα και χρησιμοποιήσαμε επίσης έναν πίνακα εισαγωγής μεγέθους N για την αποθήκευση της ακολουθίας προπαραγγελίας.