mange programmører og mine læsere har bedt mig om at dele nogle spørgsmål om binær træbaseret kodningssamtale, ligesom jeg har gjort for array, linket liste, streng, programdesign, mønstre, hash-tabel og datastruktur generelt. Denne opgave ventede faktisk i nogen tid, og den sad fast for mig at prøve at finde løsningen på hvert eneste spørgsmål, jeg kunne have samlet. Så jeg besluttede at offentliggøre listen over binære træintervju spørgsmål nu og muligvis offentliggøre løsningen som en separat artikel senere. Dette er som at oprette en grænseflade og levere implementering senere, så du ikke blokerer for andre mennesker, der er afhængige af din grænseflade (faktisk er dette en fordel ved at bruge grænsefladen i Java eller ethvert andet programmeringssprog).
Hvad er binær træ datastruktur?
når jeg kommer tilbage til et binært træ, vil jeg gerne gentage nogle af de nyttige punkter om trædatastruktur generelt, som vil hjælpe dig med at løse disse spørgsmål alene:
1) et træ er den hierarkiske datastruktur i modsætning til et array eller en sammenkædet liste, der er lineær. Dette betyder, at du kan gemme hierarkiske oplysninger ved hjælp af en trædatastruktur, som en organisationsstruktur, stamtræ osv.
2) et træ har knuder og børn. Den øverste eller første knude kaldes roden.
3) Hvis du vil visualisere, er trædatastrukturen som et omvendt træ i den virkelige verden. Jeg mener, når du ser træer omkring dig, er deres rødder i bunden, men når du tegner en trædatastruktur i programmering eller datalogi, er deres rod på toppen.
4) et binært træ er et specielt træ, hvor du højst kan få to børn. Det betyder, at en node kan enten intet barn, et barn eller to børn. De kan ikke få tre børn eller mere.
5) alle knudepunkter, der ikke har nogen børn, er kendt som en bladknude.
6) binært søgetræ er en speciel type binært træ, hvor værdierne for de venstre undertræer er mindre end eller lig med rod, og værdierne for noder på højre undertræer er større end eller lig med rod. Dette giver en sorteringsstruktur til et binært søgetræ, hvilket gør søgningen virkelig hurtig.
du kan også kontrollere datastrukturer og algoritmer: Deep Dive ved hjælp af Java-kursus på Udemy for at lære mere om binære søgetræer. Det er et af de bedste kurser til at opdatere dine datastruktur og algoritmer færdigheder.
7) det binære søgetræ er tæt forbundet med en binær søgning, der fungerer efter princippet om at reducere inputstørrelsen til halvdelen efter hver iteration. Dette gør søgningen virkelig hurtig, og du kan finde ethvert element i det binære søgetræ på O(logN) tid, men kun hvis træet er afbalanceret.
8) der er to måder at krydse en trædatastruktur på, dybde-først eller niveau først. I dybden-først går du ned, indtil der ikke er mere node at besøge, og så kommer du tilbage for at besøge noder på samme niveau.
mens du er i niveau order traversal, besøger du alle noder på samme niveau, før du går videre til næste niveau. Der er også pre-order, post-order og in-order traversal for binær, som bruges til at krydse noder af et binært træ. Inorder traversal er speciel, fordi den besøger alle noder i sorteret rækkefølge.
9) et balanceret binært træ er som at have et lige antal noder på hvert undertræ, hvis du har alle knudepunkterne på det eneste venstre eller højre undertræ, end dit binære træ bliver ubalanceret, og det fungerer som en linket liste som vist i diagrammet nedenfor:
10) et ubalanceret eller ikke-afbalanceret binært søgetræ fungerer som en sammenkædet liste, hvor en søgning vil tage O(n) tid i modsætning til o(logN) tid i et afbalanceret binært søgetræ.
dette er nogle af de vigtige punkter, som enhver programmør bør vide om binær træ datastruktur. Det vil hjælpe dig med at løse træbaserede kodningsproblemer. Hvis du vil lære mere om det binære træ og andre datastrukturer, foreslår jeg, at du deltager i et godt datastruktur og algoritmekursus som datastrukturer og algoritmer: Deep Dive ved hjælp af Java på Udemy til at børste dine grundlæggende.
40+ binære træ samtale spørgsmål til Java programmører
uden at spilde mere af din tid, her er min liste over binary tree og binary search tree (BST) baseret kodning problemer fra programmering jobsamtaler. Jeg har linket til løsning, hvor det er muligt, men hvis der ikke er noget link, kan du også finde en løsning ved blot at lave en Google-søgning. De er meget populære spørgsmål, og mange mennesker har allerede løst dem.
for at få mest muligt ud af denne liste skal du prøve at løse problemet, før du først undersøger løsningen, så fungerer dit sind, og du står over for udfordringer og konsoliderer din forståelse. Hvis du ser på løsningen med det samme, lærer du kun 10%, men hvis du prøver, lærer du 80 til 90% af koncepter og tricks bag hvert spørgsmål.
1) Hvordan finder du den laveste fælles forfader til et binært træ i Java? (løsning)
2) Hvordan udskriver du den venstre visning af et binært træ i Java? (løsning)
3) Skriv et program til at konstruere et træ fra Inorder og forudbestille traversal i Java? (løsning)
4) Hvordan udskriver du almindelige noder i to binære søgetræer i Java? (løsning)
5) hvorfor binary heap er et bedre valg end BST til implementering af prioritetskø? (svar)
6) Hvordan kontrollerer du, om et givet binært træ er afbalanceret eller ej? Skriv en Java-metode, der accepterer et binært træ og returnerer sandt, hvis det er afbalanceret eller falsk på anden måde. (løsning)
7) Hvad er nogle fordele ved en binær søgning træ over en hashtable datastruktur? (svar)
8) Hvordan kontrollerer du, om et givet binært træ er et undertræ af et andet binært træ? (løsning)
du har givet to binære træer, og du skal returnere sandt, hvis et første binært træ er et undertræ af det andet. Et undertræ af binært træ BT er et træ t bestående af en node fra BT og alle dets efterkommere. For eksempel er T1 i det følgende tilfælde et undertræ af binært træ BT
9) Hvordan finder du Afstanden mellem to noder i et binært træ? (løsning)
10) Hvordan finder man den laveste fælles forfader i et binært træ i Java? (løsning)
11) Skriv et Java-program for at kontrollere, om alle blade af et givet binært træ er på samme niveau? (løsning)
12) hvordan konverterer du et givet binært træ til dobbeltkædet liste i Java? (løsning)
13) Skriv et program for at finde en dybde af et givet binært træ i Java? (løsning)
14) Hvad er forskellen mellem binære og binære søgetræer? (svar)
15) Hvad er et selvbalanceret træ? (svar)
16) Hvad er AVL-træet? (svar)
17) Skriv et Java-program for at udskrive forudbestillingsgennemgang af et binært søgetræ? Giv en løsning ved hjælp af både iteration og rekursion? (løsning)
18) Udskriv post-order traversal af BST? Giv iterativ og rekursiv algoritme (løsning)
19) Udskriv inorder traversal af en BST i Java? Giv både Iterative og rekursive algoritmer (løsning)
20) Du har givet en BST, hvor to noder byttes? Hvordan gendanner du den oprindelige BST? (løsning)
21) hvordan konverterer du et binært træ til et binært søgetræ i Java? (løsning)
22) Find det største BST-undertræ af et givet binært træ i Java? (løsning)
23) Skriv et Java-program for at forbinde noder på samme niveau som et binært træ? (løsning)
24) Hvad er en Trie datastruktur? (svar)
25) Hvad er forskellen mellem det binære træ og Trie? (svar)
26) Udskriv forfædre til en given node af et binært træ i Java? (løsning)
27) Skriv et Java-program for at udskrive niveauet for en given node i et binært træ? (løsning)
28) Udskriv almindelige noder af to givne BST i Java? (løsning)
29) Giv et binært træ, udskrive alle rod-til-blad sti i Java? (løsning)
30) Udskriv iordre træ traversal uden rekursion i Java? (løsning)
31) Udskriv forudbestilling træ gennemløb uden rekursion og stak i Java? (løsning)
32) Udskriv postordre træ traversal uden rekursion i Java? (løsning)
33) Java-Program for at kontrollere, om et givet binært træ er BST eller ej? (løsning)
34) Skriv et Java-Program for at tælle bladknudepunkter i et binært træ? (løsning)
35) Skriv et Java-program for at finde højden eller dybden af et binært træ? (løsning)
36) hvordan finder du ud af, om to givne binære træer er ens? (løsning)
Skriv en metode i Java, som vil acceptere to binære træer og returnere sand, hvis de er de samme, ellers returnere falsk.
37) hvordan sletter du en given node fra et binært søgetræ i Java? (løsning)
38) Skriv en Java-funktion for at tilføje en given node i et binært søgetræ? (løsning)
39) Udskriv et binært træ i lodret rækkefølge i Java? (løsning)
40) hvad er den rød-sorte træ datastruktur? (svar)
svar – Rød-sort træ er et selvbalancerende binært søgetræ (BST), hvor hver node har følgende egenskaber
a) hver node har en farve, enten rød eller sort.
b) træets rod er altid sort.
c) der er ikke to tilstødende røde noder (en rød knude kan ikke have en rød forælder eller et rødt barn).
d) hver sti fra roden til en NULL node har det samme antal sorte noder.
du kan også tjekke datastrukturer i Java: et genopfriskningskursus om pædagogisk for at lære mere om Rød sort træ datastruktur.
det er alt på denne liste over top 40 binære træer og binære søgetræbaserede kodningsproblemer fra programmeringssamtaler. Selvom løsningen er givet i Java programmeringssprog, er du velkommen til at løse disse spørgsmål på ethvert programmeringssprog efter eget valg som Python, C, C++, JavaScript, Ruby eller endda hurtig. Du kan også sende din løsning i kommentarfeltet, så samfundet kan gennemgå din løsning og give nogle nyttige feedback.
alt det bedste til din kodningssamtale.
Yderligere Læring
11 Væsentlige Kodningsspørgsmål.
Master Kodningssamtalen: datastrukturer + algoritmer
Grokking Kodningssamtalen: Mønstre for kodning spørgsmål
andre kodning samtale spørgsmål l du kan lide
- Sådan implementeres indsættelsessorteringsalgoritmen i Java? (tutorial)
- hvordan anvendes Hurtigsortalgoritmen på plads i Java? (tutorial)
- Sådan implementeres Boblesorteringsalgoritmen i Java? (tutorial)
- forskel mellem sammenligning og ikke-Sammenligning baseret sortering algoritme? (svar)
- Hvordan søger Bucket Sort i Java? (tutorial)
- Sådan implementeres Hurtigsortalgoritme uden rekursion? (tutorial)
- Sådan udføres en binær søgealgoritme i Java? (tutorial)
- Sådan finder du alle par i et array, hvis sum er lig med k (løsning)
- Sådan fjerner du dubletter fra et array i Java? (løsning)
- Sådan finder du det mest betydningsfulde og mindste tal i et array uden sortering? (løsning)
- Sådan finder du dubletter fra et usorteret array i Java? (løsning)
- Sådan finder du et manglende nummer i et sorteret array? (løsning)
- Hvordan finder man en manglende værdi fra et array indeholdende 1 til 100? (løsning)
- 50+ datastruktur og algoritmer problemer fra samtaler (spørgsmål)
- mine foretrukne gratis kurser til at lære datastruktur i dybden (FreeCodeCamp)
- Sådan fjerner du et element fra et array i Java? (løsning)
- Sådan kontrolleres, om et array indeholder en bestemt værdi? (løsning)
- 10 Gratis datastruktur og algoritme kurser for programmører (kurser)
- 100 + datastruktur Kodningsproblemer fra samtaler (spørgsmål)
tak for at læse denne artikel. Hvis du kan lide denne artikel, så del den med dine venner og kolleger. Hvis du har spørgsmål eller feedback, så send en note.
P. S. – Hvis du leder efter nogle gratis Algoritmekurser for at forbedre din forståelse af datastruktur og algoritmer, skal du også kontrollere kurset Easy to Advanced Data Structures på Udemy. Det er skrevet af en Google ingeniør og algoritme ekspert, og det er helt gratis.