Saltar al contenido

Invertir un árbol binario (de izquierda a derecha)

Solución:

Puede utilizar la recursividad. Intercambiamos el elemento secundario izquierdo y derecho de un nodo, en el lugar, y luego hacemos lo mismo con sus elementos secundarios:

static void reverseTree(final TreeNode root) {
    final TreeNode temp = root.right;
    root.right = root.left;
    root.left = temp;
    
    if (root.left != null) {
        reverseTree(root.left);
    }
    
    if (root.right != null) {
        reverseTree(root.right);
    }
}

Para manejar el caso donde el parámetro root puede ser nulo:

static void reverseTree(final TreeNode root) {
    if (root == null) {
        return;
    }
    
    final TreeNode temp = root.right;
    root.right = root.left;
    root.left = temp;
    
    reverseTree(root.left);
    
    reverseTree(root.right);
}

Invierta un árbol binario en O (1) en C / C ++.

struct NormalNode {
  int value;
  struct NormalNode *left;
  struct NormalNode *right;
};

struct ReversedNode {
  int value;
  struct ReversedNode *right;
  struct ReversedNode *left;
};

struct ReversedNode *reverseTree(struct NormalNode *root) {
  return (struct ReversedNode *)root;
}

Hay un par de partes interesantes en esta pregunta. Primero, dado que su lenguaje es Java, es más probable que tenga un nodo genérico clase, algo como esto:

class Node<T> {
    private final T data;
    private final Node left;
    private final Node right;
    public Node<T>(final T data, final Node left, final Node right) {
        this.data  = data;
        this.left  = left;
        this.right = right;
    }
    ....
}

En segundo lugar, la inversión, a veces llamada inversión, se puede hacer mutando los campos izquierdo y derecho del nodo, o creando un nuevo nodo como el original pero con sus hijos izquierdo y derecho “invertidos”. El primer enfoque se muestra en otra respuesta, mientras que el segundo enfoque se muestra aquí:

class Node<T> {
    // See fields and constructor above...

    public Node<T> reverse() {
        Node<T> newLeftSubtree = right == null ? null : right.reverse();
        Node<T> newRightSubtree = left == null ? null : left.reverse();
        return Node<T>(data, newLeftSubtree, newRightSubtree); 
    }
}

La idea de no mutar una estructura de datos es una de las ideas detrás de las estructuras de datos persistentes, que son bastante interesantes.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

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