Categorías
Algorithms Interview

LeetCode: rellenar los punteros siguientes a la derecha en cada nodo II (Java)

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;
    }
}
  Suma máxima de subarreglos cerca de K

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *