Å reversere et binært tre i Java

1. Oversikt

Å reversere et binært tre er et av problemene vi kan bli bedt om å løse under et teknisk intervju.

I denne raske opplæringen vil vi se et par forskjellige måter å løse dette problemet på.

2. Binært tre

Et binært tre er en datastruktur der hvert element maksimalt har to barn, som er referert til som venstre barn og høyre barn. Det øverste elementet i treet er rotnoden, mens barna er innvendige noder.

Derimot, hvis en node ikke har noe barn, kalles det et blad.

Når det er sagt, la oss lage vårt objekt som representerer en node:

offentlig klasse TreeNode {private int-verdi; private TreeNode rightChild; privat TreeNode leftChild; // Getters og setters}

La oss deretter lage treet vårt som vi skal bruke i eksemplene våre:

 TreeNode leaf1 = ny TreeNode (1); TreeNode leaf2 = ny TreeNode (3); TreeNode leaf3 = ny TreeNode (6); TreeNode leaf4 = ny TreeNode (9); TreeNode nodeRight = ny TreeNode (7, leaf3, leaf4); TreeNode nodeLeft = ny TreeNode (2, blad1, blad2); TreeNode rot = ny TreeNode (4, nodeLeft, nodeRight); 

I den forrige metoden opprettet vi følgende struktur:

Ved å snu treet fra venstre mot høyre, vil vi ende opp med å ha følgende struktur:

3. Å reversere det binære treet

3.1. Rekursiv metode

I det første eksemplet, vi bruker rekursjon for å reversere treet.

Først av alt, vi vil kalle metoden vår ved hjelp av treets rot, så bruker vi den på henholdsvis venstre og høyre barn til vi når treets blader:

public void reverseRecursive (TreeNode treeNode) {if (treeNode == null) {return; } TreeNode temp = treeNode.getLeftChild (); treeNode.setLeftChild (treeNode.getRightChild ()); treeNode.setRightChild (temp); reverseRecursive (treeNode.getLeftChild ()); reverseRecursive (treeNode.getRightChild ()); }

3.2. Iterativ metode

I det andre eksemplet, vi vil reversere treet ved hjelp av en iterativ tilnærming. For det, vi skal bruke en LinkedList, som vi initialiserer med roten til treet vårt.

Deretter, for hver node vi undersøker fra listen, legger vi barna til den listen før vi permuterer dem.

Vi fortsetter å legge til og fjerne fra LinkedList til vi når treets blader:

public void reverseIterative (TreeNode treeNode) {List kø = ny LinkedList (); hvis (treeNode! = null) {queue.add (treeNode); } mens (! queue.isEmpty ()) {TreeNode node = queue.poll (); hvis (node.getLeftChild ()! = null) {queue.add (node.getLeftChild ()); } hvis (node.getRightChild ()! = null) {queue.add (node.getRightChild ()); } TreeNode temp = node.getLeftChild (); node.setLeftChild (node.getRightChild ()); node.setRightChild (temp); }}

4. Konklusjon

I denne raske artikkelen undersøkte vi de to måtene å reversere et binært tre. Vi har startet med å bruke en rekursiv metode for å reversere den. Så endte vi opp med å bruke en iterativ måte å oppnå det samme resultatet på.

Den komplette kildekoden til disse eksemplene og enhetstesttilfeller finner du på Github.


$config[zx-auto] not found$config[zx-overlay] not found