Haga un seguimiento del problema «Rellenar los punteros siguientes a la derecha en cada nodo».
¿Y si el árbol dado pudiera ser cualquier árbol binario? ¿Seguiría funcionando su solución anterior?
Análisis
De manera similar a Poblar los punteros siguientes a la derecha en cada nodo, tenemos 4 punteros en 2 niveles del árbol.
Solución Java
public void connect(TreeLinkNode root) { if(root == null) return; TreeLinkNode lastHead = root;//prevous level's head TreeLinkNode lastCurrent = null;//previous level's pointer TreeLinkNode currentHead = null;//currnet level's head TreeLinkNode current = null;//current level's pointer while(lastHead!=null){ lastCurrent = lastHead; while(lastCurrent!=null){ //left child is not null if(lastCurrent.left!=null) { if(currentHead == null){ currentHead = lastCurrent.left; current = lastCurrent.left; }else{ current.next = lastCurrent.left; current = current.next; } } //right child is not null if(lastCurrent.right!=null){ if(currentHead == null){ currentHead = lastCurrent.right; current = lastCurrent.right; }else{ current.next = lastCurrent.right; current = current.next; } } lastCurrent = lastCurrent.next; } //update last head lastHead = currentHead; currentHead = null; } } |