Categorías
Algorithms

LeetCode – Serializar y deserializar árbol binario (Java)

Diseñe un algoritmo para serializar y deserializar un árbol binario. No hay restricciones sobre cómo debería funcionar su algoritmo de serialización / deserialización. Solo necesita asegurarse de que un árbol binario se pueda serializar en una cadena y esta cadena se pueda deserializar en la estructura de árbol original.

Solución Java 1 – Traveral de orden de nivel

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    ArrayList<String> list = new ArrayList<>();
    LinkedList<TreeNode> q = new LinkedList<>();
    q.offer(root);
 
    while (!q.isEmpty()) {
        TreeNode h = q.poll();
        if (h == null) {
            list.add("#");
        } else {
            list.add("" + h.val);
            q.offer(h.left);
            q.offer(h.right);
        }
    }
 
    return String.join(",", list);
}
 
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] arr = data.split(",");
    if (arr[0].equals("#")) {
        return null;
    }
 
    TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
    LinkedList<TreeNode> q = new LinkedList<>();
    q.offer(root);
 
    int i = 1;
 
    while (!q.isEmpty()) {
        TreeNode h = q.poll();
        if (h != null) {
            TreeNode left = null;
            if (!arr[i].equals("#")) {
                left = new TreeNode(Integer.parseInt(arr[i]));
            }
            h.left = left;
            q.offer(left);
            i++;
 
            TreeNode right = null;
            if (!arr[i].equals("#")) {
                right = new TreeNode(Integer.parseInt(arr[i]));
            }
            h.right = right;
            q.offer(right);
            i++;
        }
    }
 
    return root;
}
  LeetCode - Validar árbol de búsqueda binaria (Java)

Solución de Java 2: Preorder Traversal

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    if(root==null)
        return null;
 
    Stack<TreeNode> stack = new Stack<TreeNode>();
    stack.push(root);
    StringBuilder sb = new StringBuilder();
 
    while(!stack.isEmpty()){
        TreeNode h = stack.pop();   
        if(h!=null){
            sb.append(h.val+",");
            stack.push(h.right);
            stack.push(h.left);  
        }else{
            sb.append("#,");
        }
    }
 
    return sb.toString().substring(0, sb.length()-1);
}
 
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if(data == null)
        return null;
 
    int[] t = {0};
    String[] arr = data.split(",");
 
    return helper(arr, t);
}
 
public TreeNode helper(String[] arr, int[] t){
    if(arr[t[0]].equals("#")){
        return null;
    }
 
    TreeNode root = new TreeNode(Integer.parseInt(arr[t[0]]));
 
    t[0]=t[0]+1;
    root.left = helper(arr, t);
    t[0]=t[0]+1;
    root.right = helper(arr, t);
 
    return root;
}

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 *