Umkehren eines Binärbaums in Java

1. Übersicht

Das Umkehren eines Binärbaums ist eines der Probleme, die wir möglicherweise während eines technischen Interviews lösen müssen .

In diesem kurzen Tutorial sehen wir verschiedene Möglichkeiten, um dieses Problem zu lösen.

2. Binärer Baum

Ein Binärbaum ist eine Datenstruktur, in der jedes Element höchstens zwei Kinder hat , die als linkes Kind und rechtes Kind bezeichnet werden. Das oberste Element des Baums ist der Wurzelknoten, während die untergeordneten Knoten die inneren Knoten sind .

Allerdings , wenn ein Knoten kein Kind hat, ist es ein Blatt genannt.

Nachdem dies gesagt ist, erstellen wir unser Objekt, das einen Knoten darstellt:

public class TreeNode { private int value; private TreeNode rightChild; private TreeNode leftChild; // Getters and setters }

Dann erstellen wir unseren Baum, den wir in unseren Beispielen verwenden werden:

 TreeNode leaf1 = new TreeNode(1); TreeNode leaf2 = new TreeNode(3); TreeNode leaf3 = new TreeNode(6); TreeNode leaf4 = new TreeNode(9); TreeNode nodeRight = new TreeNode(7, leaf3, leaf4); TreeNode nodeLeft = new TreeNode(2, leaf1, leaf2); TreeNode root = new TreeNode(4, nodeLeft, nodeRight); 

In der vorherigen Methode haben wir die folgende Struktur erstellt:

Wenn Sie den Baum von links nach rechts umkehren, erhalten Sie die folgende Struktur:

3. Umkehren des Binärbaums

3.1. Rekursive Methode

Im ersten Beispiel verwenden wir die Rekursion, um den Baum umzukehren .

Zuerst rufen wir unsere Methode mit der Wurzel des Baums auf, dann wenden wir sie auf das linke und das rechte Kind an, bis wir die Blätter des Baumes erreichen:

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. Iterative Methode

Im zweiten Beispiel kehren wir den Baum mit einem iterativen Ansatz um. Dafür verwenden wir eine LinkedList , die wir mit der Wurzel unseres Baums initialisieren .

Dann fügen wir für jeden Knoten, den wir aus der Liste abfragen, seine untergeordneten Knoten zu dieser Liste hinzu, bevor wir sie permutieren .

Wir fügen der LinkedList so lange hinzu und entfernen sie, bis wir die Blätter des Baumes erreichen:

public void reverseIterative(TreeNode treeNode) { List queue = new LinkedList(); if(treeNode != null) { queue.add(treeNode); } while(!queue.isEmpty()) { TreeNode node = queue.poll(); if(node.getLeftChild() != null){ queue.add(node.getLeftChild()); } if(node.getRightChild() != null){ queue.add(node.getRightChild()); } TreeNode temp = node.getLeftChild(); node.setLeftChild(node.getRightChild()); node.setRightChild(temp); } }

4. Fazit

In diesem kurzen Artikel haben wir die beiden Möglichkeiten zum Umkehren eines Binärbaums untersucht. Wir haben damit begonnen, eine rekursive Methode zu verwenden, um sie umzukehren. Dann haben wir einen iterativen Weg gewählt, um das gleiche Ergebnis zu erzielen.

Den vollständigen Quellcode dieser Beispiele und Unit-Testfälle finden Sie auf Github.