Reconstruir un árbol binario a partir de sus recorridos inorden y postorden es un ejercicio clásico en estructuras de datos que nos permite entender mejor cómo funcionan estos recorridos y cómo se relacionan con la estructura del árbol. Para abordar este problema, partimos de dos listas que representan el recorrido inorden y el postorden de un árbol dado.
El primer paso fundamental es identificar la raíz del árbol. Sabemos que en el recorrido postorden, el último elemento siempre es la raíz, porque este recorrido visita primero el subárbol izquierdo, luego el derecho y finalmente la raíz. Por ejemplo, si el último elemento del postorden es el número 1, entonces ese será el nodo raíz de nuestro árbol.
Una vez que tenemos la raíz, la siguiente tarea es localizarla en el recorrido inorden. Esto es crucial porque el recorrido inorden visita primero el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho. Por lo tanto, todos los elementos que aparecen a la izquierda de la raíz en el recorrido inorden corresponden al subárbol izquierdo, y todos los que aparecen a la derecha corresponden al subárbol derecho.
Con esta información, podemos dividir el recorrido inorden en dos partes: la parte izquierda para el subárbol izquierdo y la parte derecha para el subárbol derecho. Sin embargo, para reconstruir completamente el árbol, también necesitamos dividir el recorrido postorden en las partes correspondientes a los subárboles izquierdo y derecho. Aquí es donde el recorrido inorden nos ayuda, porque nos indica cuántos elementos pertenecen a cada subárbol.
Por ejemplo, si en el recorrido inorden el subárbol derecho tiene tres elementos, entonces en el recorrido postorden los últimos tres elementos antes de la raíz corresponden al subárbol derecho, y el resto al subárbol izquierdo. Así, podemos separar el postorden en dos segmentos que coinciden con los subárboles izquierdo y derecho.
Este proceso se repite de forma recursiva para cada subárbol. Tomamos el segmento correspondiente del recorrido inorden y postorden, identificamos la raíz del subárbol (último elemento del postorden), la localizamos en el inorden para dividir en sub-subárboles izquierdo y derecho, y así sucesivamente hasta que llegamos a nodos hoja, que son aquellos que no tienen elementos a la izquierda ni a la derecha en el recorrido inorden.
Para ilustrar este proceso, imaginemos que tenemos un subárbol con recorrido inorden [4, 2, 5] y postorden [4, 5, 2]. El último elemento del postorden es 2, que será la raíz de este subárbol. En el recorrido inorden, 2 está en medio, con 4 a la izquierda y 5 a la derecha. Por lo tanto, 4 será el hijo izquierdo y 5 el hijo derecho de 2. Como 4 y 5 no tienen más elementos a su izquierda o derecha, serán nodos hoja.
De forma similar, para otro subárbol con inorden [6, 3, 7] y postorden [6, 7, 3], la raíz es 3. En el inorden, 6 está a la izquierda y 7 a la derecha, por lo que 6 y 7 serán los hijos izquierdo y derecho de 3, respectivamente, y ambos serán hojas si no tienen más elementos.
Este método nos permite reconstruir el árbol completo paso a paso, siempre identificando la raíz a partir del postorden, dividiendo el inorden para separar los subárboles y segmentando el postorden en consecuencia. La clave está en la recursividad, que nos permite aplicar el mismo procedimiento a cada subárbol hasta que no queden más nodos por procesar.
Para implementar esta lógica en código, podemos definir una función recursiva que reciba los recorridos inorden y postorden, identifique la raíz, divida los recorridos en sub-recorridos para los hijos izquierdo y derecho, y construya el árbol nodo a nodo. Un ejemplo en Java podría ser:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
private TreeNode build(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return null;
}
int rootVal = postorder[postEnd];
TreeNode root = new TreeNode(rootVal);
int inRootIndex = inStart;
while (inorder[inRootIndex] != rootVal) {
inRootIndex++;
}
int leftTreeSize = inRootIndex - inStart;
root.left = build(inorder, inStart, inRootIndex - 1,
postorder, postStart, postStart + leftTreeSize - 1);
root.right = build(inorder, inRootIndex + 1, inEnd,
postorder, postStart + leftTreeSize, postEnd - 1);
return root;
}
En este código, buscamos la raíz en el postorden, localizamos su posición en el inorden para determinar el tamaño del subárbol izquierdo, y luego llamamos recursivamente para construir los subárboles izquierdo y derecho.
Practicar este tipo de ejercicios es muy recomendable, ya que ayuda a entender mejor la relación entre los diferentes recorridos de un árbol y cómo se puede reconstruir la estructura original a partir de ellos. Además, es un tema que suele aparecer en exámenes y entrevistas técnicas, por lo que dominarlo nos será muy útil.