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.

---

---

Utiliza Nuestro Buscador