Inversión de un árbol binario en Java

1. Información general

La inversión de un árbol binario es uno de los problemas que se nos podría pedir que resolvamos durante una entrevista técnica .

En este tutorial rápido, veremos un par de formas diferentes de resolver este problema.

2. Árbol binario

Un árbol binario es una estructura de datos en la que cada elemento tiene como máximo dos hijos , que se denominan hijo izquierdo y hijo derecho. El elemento superior del árbol es el nodo raíz, mientras que los hijos son los nodos interiores .

Sin embargo, si un nodo no tiene un hijo, se llama hoja.

Dicho esto, creemos nuestro objeto que representa un nodo:

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

Luego, creemos nuestro árbol que usaremos en nuestros ejemplos:

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

En el método anterior, creamos la siguiente estructura:

Al invertir el árbol de izquierda a derecha, terminaremos teniendo la siguiente estructura:

3. Inversión del árbol binario

3.1. Método recursivo

En el primer ejemplo, usaremos la recursividad para invertir el árbol .

En primer lugar, llamaremos a nuestro método usando la raíz del árbol, luego lo aplicaremos en los hijos izquierdo y derecho respectivamente hasta llegar a las hojas del árbol:

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. Método iterativo

En el segundo ejemplo, invertiremos el árbol mediante un enfoque iterativo. Para eso, usaremos una LinkedList , que inicializamos con la raíz de nuestro árbol .

Luego, para cada nodo que sondeamos de la lista, agregamos sus hijos a esa lista antes de permutarlos .

Seguimos agregando y eliminando de LinkedList hasta llegar a las hojas del árbol:

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. Conclusión

En este artículo rápido, exploramos las dos formas de invertir un árbol binario. Comenzamos usando un método recursivo para revertirlo. Luego, terminamos usando una forma iterativa para lograr el mismo resultado.

El código fuente completo de estos ejemplos y casos de prueba unitaria se puede encontrar en Github.