LeetCode: verificar la serialización de pedidos anticipados de un árbol binario (Java)

Una forma de serializar un árbol binario es utilizar el recorrido de preorden. Cuando encontramos un nodo no nulo, registramos el valor del nodo. Si es un nodo nulo, registramos usando un valor centinela como #.

      9
    /   
   3     2
  /    / 
 4   1  #  6
/  /    / 
# # # #   # #

Por ejemplo, el árbol binario anterior se puede serializar en la cadena «9,3,4, #, #, 1, #, #, 2, #, 6, #, #», donde # representa un nodo nulo.

Dada una cadena de valores separados por comas, verifique si es una serialización transversal de preorden correcta de un árbol binario. Encuentre un algoritmo sin reconstruir el árbol.

Solución Java

Podemos seguir recortando las hojas hasta que no haya nadie a quien quitar. Si una secuencia es como «4 # #», cámbiela a «#» y continúe. Una pila es una buena estructura de fechas para este propósito.

Aquí hay un ejemplo:

public boolean isValidSerialization(String preorder) {
    LinkedList<String> stack = new LinkedList<String>();
    String[] arr = preorder.split(",");
 
    for(int i=0; i<arr.length; i++){
        stack.add(arr[i]);
 
        while(stack.size()>=3 
            && stack.get(stack.size()-1).equals("#")
            && stack.get(stack.size()-2).equals("#")
            && !stack.get(stack.size()-3).equals("#")){
 
            stack.remove(stack.size()-1);
            stack.remove(stack.size()-1);
            stack.remove(stack.size()-1);
 
            stack.add("#");
        }
 
    }
 
    if(stack.size()==1 && stack.get(0).equals("#"))
        return true;
    else
        return false;
}

LeetCode - Poder de dos (Java)

Si solo se permiten operaciones de pila, la solución se puede escribir de la siguiente manera:

public boolean isValidSerialization(String preorder) {
    String[] arr = preorder.split(",");
 
    Stack<String> stack = new Stack<>();
    for(String s: arr){
        if(stack.isEmpty() || !s.equals("#")){
            stack.push(s);
        }else{
            while(!stack.isEmpty() && stack.peek().equals("#")){
                stack.pop();
                if(stack.isEmpty()){
                    return false;
                }else{
                    stack.pop();
                }
            }
            stack.push("#");
        }            
    }
 
    return stack.size()==1 && stack.peek().equals("#");
}

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta