¿Cuál es el enfoque algorítmico para invertir un árbol binario dado?

Hay un enfoque iterativo elegante para este problema. El enfoque se asemeja a una búsqueda de amplitud en la que utilizamos una Cola para atravesar todos los nodos.

Objetivo: atravesar todos los nodos, de arriba a abajo, nivel por nivel, en cada paso, intercambiando los subárboles izquierdo y derecho del nodo.

Suposición: familiaridad con las colas y la definición de datos para un árbol (consulte el código a continuación).

Definición para árbol binario
clase TreeNode {
int val;
TreeNode se fue;
TreeNode a la derecha;
TreeNode (int x) {val = x; }
}

Enfoque:

• Cree una cola para almacenar nodos cuyo elemento secundario izquierdo y derecho aún no se hayan intercambiado. Como una cola es una interfaz, no puede construir una cola directamente. La mejor opción es construir una clase que ya implementa la interfaz de cola (es decir, LinkedList).

Queue queue = new LinkedList ();

• Antes de recorrer la cola, agregue el nodo raíz. Esto le proporciona un punto de partida para sus inversiones. El primer “intercambio” que harás es para los subárboles izquierdo y derecho del nodo raíz.

queue.add (root);

• Mientras la cola no esté vacía, elimine el siguiente nodo de la cola, intercambie sus elementos secundarios y agregue los elementos secundarios a la cola. Por la naturaleza de la adhesión de una cola al primero en entrar, primero en salir, el “intercambio” se realizará nivel por nivel. Los nodos del siguiente nivel no se tocarán hasta que el nivel anterior haya completado todos sus “intercambios”.

while (! queue.isEmpty ()) {
// “abre” el primer nodo
TreeNode current = queue.poll ();

// intercambiando los subárboles izquierdo y derecho
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;

// Los nodos nulos no se agregan a la cola
if (current.left! = null) queue.add (current.left);
if (current.right! = null) queue.add (current.right);
}

• Devolvemos la raíz una vez que la Cola esté vacía y todos los elementos secundarios hayan sido intercambiados.

PD. Como de costumbre, ¡no olvides hacer un cheque nulo!

público TreeNode invertTree (raíz de TreeNode) {
if (root == null) return null; // línea 1

if (root.left! = null) {// línea 2
TreeNode leftchild = invertTree (root.left); // línea 3
leftchild .right = root; // línea 4
}

if (root.right! = null) {// línea 5
TreeNode rightchild = invertTree (root.right); // línea 6
rightchild.left = root; // línea 7
}

root.left = null; // línea 8
root.right = nulo; // línea 9

volver root; // línea 10
}

Considera la estructura
1
/ \
2 3
/ \ \
4 5 6

Si el nodo suministrado inicialmente es nulo, la línea 1 devolverá nulo.

Una vez que el control pasa la línea 1, la línea 2 determinará si el nodo ha salido del niño.

Para la estructura de árbol anterior, el nodo inicial suministrado será 1 (implica que estamos a través de la línea 1)
Como 1 ha salido del hijo, la línea 3 se ejecutará y la pila se verá como

2 (arriba)
1

Como tenemos un nodo (2) que no es nulo, pasamos por la línea 1
2 tiene un hijo izquierdo (4), por lo que estamos en la línea 3 y la pila ahora se ve como

4 (arriba)
2
1

Como tenemos un nodo (4) que no es nulo, pasamos por la línea 1
El nodo (4) no tiene hijo izquierdo o derecho, por lo que el método devuelve el nodo 4 en la línea 10.

pila parece

2 (arriba)
1

tenemos un resultado de la línea 3 (leftchild = 4)
la línea 4 asignará el nodo raíz actual (2) como el hijo derecho de 4.

NB: una vez que se invierte el árbol, los enlaces se invierten con la relación padre-hijo.

Nueva estructura se verá como

4 4
\
2

Pasando a la línea 5, tenemos nuestro nodo raíz actual como 2 con su hijo derecho como 5.

pila se ve a continuación una vez que estamos en la línea 6
5 (arriba)
2
1

Una vez más, el nodo (5) no tiene elementos secundarios, por lo que la línea 10 devolverá el nodo 5

la pila se ve a continuación con el resultado de la línea 6 (rightchild = 5)
2 (arriba)
1

la línea 7 asignará el nodo raíz actual (2) como el hijo izquierdo del nodo (5)

Nueva estructura se verá como

4 5
\ /
2

las líneas 8 y 9 borrarán los elementos secundarios del nodo (2).
la línea 10 devolverá el nodo raíz actual (2)

stack se ve a continuación con el resultado de la línea 3 (leftchild = 2). El nodo raíz actual es 1

1 (arriba)

la línea 4 asignará el nodo actual (1) como el hijo derecho del resultado (leftchild = 2) de la línea 3

Nueva estructura se verá como

4 5
\ /
2
\
1

Avanzando en la línea 5 (1 tiene el hijo derecho que 3) y luego avanzando a la línea 6

la pila se ve a continuación una vez que estamos en la línea 6

3 (arriba)
1

Como 3 no tiene un hijo izquierdo, la línea 2 falla. Pasando a la línea 5 y a la línea 6.

la pila se ve a continuación una vez que estamos en la línea 6

6 (arriba)
3
1

Como 6 no tiene elementos secundarios, se devuelve el nodo 6 y el

la pila se ve a continuación una vez que estamos en la línea 6 (rightchild = 6)

3 (arriba)
1

en la línea 7

Nueva estructura se verá como

4 5 6
\ / /
2 3
\
1

NB: ambas estructuras no están conectadas. el nodo (1) todavía tiene su hijo izquierdo apuntando a 2 y su hijo derecho apuntando
a 3. Esto se limpia en las líneas 8 y 9.

la línea 10 devuelve el nodo 3.
Volver a la línea 6 donde el nodo raíz actual 1.

la línea 7 asignará el nodo (1) como el hijo izquierdo del nodo 3.

Nueva estructura se verá como

4 5 6
\ / /
2 3
\ /
1

las líneas 8 y 9 borrarán los elementos secundarios del nodo (1) y devolverán el nodo 1.

No puede invertir un árbol binario algorítmicamente porque, por definición, siempre hay varios elementos secundarios y solo 1 raíz.
Es una pregunta capciosa.
Puede invertir algunos pocos árboles binarios específicos, que nunca tienen más de 1 hijo, pero NO el ejemplo que mostró. En su ejemplo, originalmente 2 es hijo de 1 y no tuvo hijos. En la forma invertida, 2 es un hijo de 4 y comparte un hijo con 3, lo cual no está permitido en absoluto en un árbol binario.

/ **

* Definición para un nodo de árbol binario.

* struct TreeNode {

* int val;

* struct TreeNode * left;

* struct TreeNode * right;

*};

* /

struct TreeNode * invertTree (struct TreeNode * root) {

if (raíz == NULL)

devuelve NULL;

más

{

struct TreeNode * temp = root-> right;

root-> right = invertTree (root-> left);

root-> left = invertTree (temp);

volver root;

}

}

Invertir un árbol no significa simplemente darle la vuelta. Sin embargo, si gira su árbol “invertido” para que la raíz esté en su posición correcta, tendrá todos los nodos secundarios invertidos.

A continuación se muestra un algoritmo puramente recursivo para hacer esto:

función reverseTree (cabeza BTNode) DEVOLUCIONES BTNode
SI cabeza = nulo ENTONCES
VOLVER nulo
MÁS
VOLVER makeNode (head.data,
reverseTree (head.right),
reverseTree (head.left))
TERMINARA SI
Función END

Tenga en cuenta que esta función crea una copia del árbol original con todos los elementos invertidos. Si tiene recolección de basura, simplemente escriba

root = reverseTree (root)

y el recolector de basura limpiará el viejo árbol. De lo contrario, tendrá que escribir e invocar una rutina de “limpieza” si desea deshacerse del árbol original:

t = raíz
root = reverseTree (root)
deleteTree (t)

Todo lo que se requiere es cambiar la dirección de los punteros.
Si se supone que el nodo A tiene B y C como su nodo izquierdo y derecho, cambie los punteros de tal manera que el nodo izquierdo de C y el nodo derecho de B apunten a A.
Además, no olvide inicializar los elementos secundarios de la raíz original en nulo.

nodo * invertBinaryTree (nodo * raíz) {
if (! root)
devuelve 0;

if (! root-> left &&! root-> right)
volver root;

nodo * l = invertBinaryTree (raíz-> izquierda);
si (l)
l-> right = root;

nodo * r = invertBinaryTree (root-> right);
si (r)
r-> izquierda = raíz;

volver root;
}
int main () {
nodo * root = newNode (A);
root-> left = newNode (B);
root-> right = newNode (C);
invertBinaryTree (root);
root-> left = root-> right = NULL;
}

Este árbol se puede revertir fácilmente al pasar el puntero principal a cada llamada en el recorrido del postorder. Pero el problema con este problema es qué devolver como respuesta.

por ejemplo:

1

/ \

2 3

al revertir será

2 3

\ /

1

Entonces, ¿qué hay que devolver 2 o 3?

o si solo podemos usar tablas hash para revertir los punteros.

Invertir vacío (raíz del nodo) {

Nodo temp = root.Left;

root.Left = root.Right;

root.Right = temp;

if (root.Left! = null)

Invertir (raíz izquierda);

if (root.Right! = null)

Invertir (root.Right);

}

Podemos usar un algoritmo recursivo como el anterior para invertir el árbol.

¿Estás seguro de la pregunta? El invertido no parece un árbol, ya que los hermanos 2 y 3 tienen un descendiente común 1.