Обръщане на двоично дърво в Java

1. Общ преглед

Обръщането на двоично дърво е един от проблемите, които може да бъдем помолени да решим по време на техническо интервю .

В този бърз урок ще видим няколко различни начина за решаване на този проблем.

2. Двоично дърво

Двоично дърво е структура от данни, при която всеки елемент има най-много две деца , които се наричат ​​ляво дете и дясно дете. Най-горният елемент на дървото е коренният възел, докато децата са вътрешните възли .

Ако обаче възел няма дете, това се нарича лист.

Като казахме това, нека създадем нашия обект, който представлява възел:

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

След това нека създадем нашето дърво, което ще използваме в нашите примери:

 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); 

В предишния метод създадохме следната структура:

Като обърнем дървото отляво надясно, ще получим следната структура:

3. Обръщане на двоичното дърво

3.1. Рекурсивен метод

В първия пример ще използваме рекурсия, за да обърнем дървото .

На първо място, ще извикаме нашия метод, като използваме корена на дървото, след което ще го приложим съответно отляво и отдясно, докато достигнем листата на дървото:

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. Итеративен метод

Във втория пример ще обърнем дървото, използвайки итеративен подход. За това ще използваме LinkedList , който инициализираме с корена на нашето дърво .

След това, за всеки възел, който анкетираме от списъка, ние добавяме неговите потомци към този списък, преди да ги пермутираме .

Продължаваме да добавяме и премахваме от LinkedList, докато достигнем листата на дървото:

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. Заключение

В тази бърза статия разгледахме двата начина за обръщане на двоично дърво. Започнахме с рекурсивен метод, за да го обърнем. След това накрая използвахме итеративен начин за постигане на същия резултат.

Пълният изходен код на тези примери и тестови случаи може да бъде намерен в Github.