LeetCode – Cruce de orden vertical de árbol binario (Java)

Dado un árbol binario, devuelve el orden vertical transversal de los valores de sus nodos. (es decir, de arriba a abajo, columna por columna).

Solución Java 1

Para cada nodo, el grado del niño izquierdo es -1 y el grado del niño derecho es +1. Podemos hacer un recorrido de orden de nivel y guardar la información del grado.

public List<List<Integer>> verticalOrder(TreeNode root) {
    TreeMap<Integer, ArrayList<Integer>> map = new TreeMap<>();
    helper(root, map);
    List<List<Integer>> result = new ArrayList<>();
    result.addAll(map.values());
    return result;
}
 
private void helper(TreeNode t, TreeMap<Integer, ArrayList<Integer>> map) {
    if (t == null) {
        return;
    }
 
    LinkedList<TreeNode> q1 = new LinkedList<>();
    LinkedList<Integer> q2 = new LinkedList<>();
    q1.offer(t);
    q2.offer(0);
 
    while (!q1.isEmpty()) {
        TreeNode node = q1.poll();
        int order = q2.poll();
 
        //add to map
        ArrayList<Integer> list = map.get(order);
        if (list == null) {
            list = new ArrayList<>();
            map.put(order, list);
        }
        list.add(node.val);
 
        if (node.left != null) {
            q1.offer(node.left);
            q2.offer(order - 1);
        }
 
        if (node.right != null) {
            q1.offer(node.right);
            q2.offer(order + 1);
        }
    }
}

LeetCode - Código Gray (Java)

La complejidad del tiempo es O (n * log (n)) y la complejidad del espacio es O (n). n es el número de nodos del árbol.

Solución Java 2

El tiempo se puede mejorar si no se usa TreeMap. Primero podemos calcular el orden mínimo y máximo del árbol. Sabemos que no debería haber ninguna brecha entre los índices.

public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if(root==null){
        return result;
    }
 
    int[] mm = new int[2];
    getMinMax(root, mm, 0);
 
    int len = mm[1]-mm[0]+1;
 
    for(int i=0; i<len; i++){
        result.add(new ArrayList<Integer>());
    }
 
    LinkedList<TreeNode> q1 = new LinkedList<>();
    LinkedList<Integer> q2 = new LinkedList<>();
 
    q1.offer(root);
    q2.offer(0);
 
    while(!q1.isEmpty()){
        TreeNode h = q1.poll();
        int order = q2.poll();
 
        result.get(order-mm[0]).add(h.val);
 
        if(h.left!=null){
            q1.offer(h.left);
            q2.offer(order-1);
        }
        if(h.right!=null){
            q1.offer(h.right);
            q2.offer(order+1);
        }
    }
 
    return result;
}
 
 
private void getMinMax(TreeNode node, int[] mm, int order){
    if(node == null){
        return;
    }
 
    mm[0] = Math.min(mm[0], order);
    mm[1] = Math.max(mm[1], order);
 
    getMinMax(node.left, mm, order-1);
    getMinMax(node.right, mm, order+1);
}

LeetCode - Encuentre K pares con las sumas más pequeñas (Java)

La complejidad del tiempo es O (n) y la complejidad del espacio es O (n). n es el número de nodos del árbol.

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta