algorithm - resueltos - Verificar si un árbol binario es una imagen especular o simétrica

reflexion especular ejemplos

Question

¿Cuál es el algoritmo básico para probar si un árbol es simétrico? Como es un árbol binario, supongo que sería una definición recursiva de géneros

La pregunta formal es a continuación:

Un árbol binario es una imagen especular de sí mismo si sus subárboles izquierdo y derecho son imágenes idénticas idénticas, es decir, el árbol binario es simétrico. Esto se explica mejor con algunos ejemplos.

  1
 / /
2   2

CIERTO

   1
  / /
 2   2
  /
   3

FALSO

     1
   /   /
  2     2
 / /   / /
4   3 3   4

CIERTO

       1
     /   /
    2     2 
   / /   / /
  3   4 3   4

FALSO

       1
     /   /
    2     2
   /       /
  3         3

CIERTO

En un lenguaje de programación de elección, defina una clase BTree / C struct y un método asociado para verificar si el árbol es una imagen especular. Para los idiomas con tipado estático, puede suponer que los valores del nodo son todos enteros.

Class/structure definition
BTree {
  BTree left;
  BTree right;
  int value;
}

Suponga que la raíz del árbol es rastreado por la persona que llama y la función isMirror () se invoca en ella.

Además, si define una clase, asegúrese de proporcionar un constructor sin argumento y métodos getter / setter si los elementos de datos no son públicamente accesibles.

Answer 1

¿Qué le parece llamar a mirrorEquals (root.left, root.right) en la siguiente función: -

boolean mirrorEquals(BTree left, BTree right) {
  if (left == null || right == null) return left == null && right == null;
  return left.value == right.value
     && mirrorEquals(left.left, right.right)
     && mirrorEquals(left.right, right.left);
}

Básicamente, compare el subárbol izquierdo y el subárbol derecho invertido, dibujando una línea imaginaria de inversión en la raíz.

Answer 2

A continuación está la solución con respecto a C- COde

isMirror(root)
{ 
Symmetric(root->left, root->right);
}

Symmetric(root1,root2)
{
 if( (root1->left EX-NOR root2->right) && (root1->right EX-NOR root2->left) && (root1->value==root2->value) )        
//exnor operation will return true if either both present or both not present 
// a EX-NOR b =(!a && !b) || (a && b))
        {
    Symmetric(root1->left, root2->right);
    Symmetric(root1->right, root2->left);
        }    
else return false;
}

Answer 3

Aquí hay una solución de C ++ por gvijay

bool isMirrorTree(BTnode* LP, BTnode* RP)
{
    if (LP == NULL || RP == NULL) // if either is null check that both are NULL
    { 
        return ( LP == NULL && RP == NULL );
    } 
    // check that data is equal and then recurse
    return LP->data == RP->data && 
           isMirrorTree( LP->left, RP->right ) && 
           isMirrorTree( LP->right, RP->left );
}

Answer 4

Enfoque ligeramente diferente.

¿Qué tal hacer un recorrido inorden del árbol binario que almacena todos los contenidos en alguna estructura de datos como una cadena / matriz.

Una vez que se completa el recorrido, comprueba si los elementos de tu conjunto forman un palíndromo. No es tan eficiente en cuanto al espacio (la recursividad toma O (log (n)), este método cuenta O (n)) pero esto también funcionará.

Answer 5

La solución recursiva de @gvijay es muy clara, y aquí hay una solución iterativa.

Inspeccione cada fila del árbol de arriba a abajo y vea si los valores son un palíndromo. Si todos son entonces, sí, es un espejo. Tendrá que implementar un algoritmo para visitar cada fila e incluir valores nulos para árboles dispersos. En pseudocódigo:

boolean isMirror(BTree tree) {
  foreach (List<Integer> row : tree.rows() {
    if (row != row.reverse()) return false;
  }
  return true;
}

El truco consiste en diseñar el algoritmo para iterar las filas de un árbol con la consideración de que los árboles dispersos deberían tener valores nulos como marcadores de posición. Esta implementación de Java parece correcta:

public static boolean isMirror(BTree root) {
  List<BTree> thisRow, nextRow;
  thisRow = Arrays.asList(root);
  while (true) {
    // Return false if this row is not a palindrome.
    for (int i=0; i<thisRow.size()/2; i++) {
      BTree x = thisRow.get(i);
      BTree y = thisRow.get(thisRow.size()-i-1);
      if ((x!=null) && (y!=null)
          && (x.value != y.value))
        return false;
      if (((x==null) && (y!=null))
          || (x!=null) && (y==null))
        return false;
    }
    // Move on to the next row.
    nextRow = new ArrayList<BTree>();
    for (BTree tree : thisRow) {
      nextRow.add((tree==null) ? null : tree.lt);
      nextRow.add((tree==null) ? null : tree.rt);
    }
    boolean allNull = true;
    for (BTree tree : nextRow) {
      if (tree != null) allNull = false;
    }
    // If the row is all empty then we''re done.
    if (allNull) return true;
    thisRow = nextRow;
  }
}

Answer 6

No tengo mucha experiencia (solo un año en la empresa), pero en mi opinión, esto se puede resolver mediante el uso de S = recursión

Por ejemplo:

MYTREECLASS B1= new MYTREECLASS();
MYTREECLASS B2= new MYTREECLASS();
B1= OriginalTree;
B2=OriginalTRee;
Boolean CHECK(MYTREECLASS, MYTREECLASS)
{
if (B1.Node = B2.Node)
then (
CHECK(B1.Left, B2.Right);
CHECK(B1.Right,B2.Left)
)
elseIf(b1.Left==null or b2.right...blah blah ,,)
return False)
else return False,

Devuelve true si coincide.

Answer 7

Si alguien necesita una versión de Swift, aquí hay una.

Otro enfoque sería simplemente invertir uno de los subárboles, y comparar los dos subárboles resultantes de una manera directa.

func compareTrees(left: TreeNode?, right: TreeNode?) -> Bool {
    var res = false
    if left == nil && right == nil {return true}
    if left != nil && right != nil {
        res = left!.val == right!.val &&
              compareTrees(left!.left, right: right!.left) &&
              compareTrees(left!.right, right: right!.right)
    }
    return res
}

func invertTree(node: TreeNode?) {
    if node == nil {return}

    var tmp = node!.left
    node!.left = node!.right
    node!.right = tmp

    invertTree(node!.left)
    invertTree(node!.right)
}

// and run it as:
if root == nil {print("Y")}
invertTree(root!.right)
compareTrees(root!.left, right: root!.right) ? print("Y") : print("N")

Answer 8

Solución iterativa usando un enfoque ligeramente diferente en Python. Use queue1 para almacenar los elementos secundarios izquierdos en orden de izquierda a derecha y queue2 para almacenar los elementos secundarios correctos de derecha a izquierda y compare para la igualdad.

def isSymmetric(root):
    if not root:
        return True
    if not (root.left or root.right):
        return True
    q1 = collections.deque([root.left])
    q2 = collections.deque([root.right])
    while q1 and q2:
        n1 = q1.popleft()
        n2 = q2.popleft()
        if n1 is None and n2 is None:
            continue
        if (n1 is None) ^ (n2 is None):
            return False
        if n1.val != n2.val:
            return False
        q1.append(n1.left)
        q1.append(n1.right)
        q2.append(n2.right)
        q2.append(n2.left)
    if not (q1 and q2):
        return True
    return False

Answer 9

clase pública SymmetricTree {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    //int[] array = {1,2,2,3,4,4,3};
    /*
     *                  1
     *                 / /
     *                /   /
     *               /     /
     *              2       2
     *             / /     / /
     *            /   /   /   /
     *           3     4 4     3
     * 
     * */
    //int[] array = {1,2};
    BinaryTree bt=new BinaryTree();
    bt.data=1;
    bt.left = new BinaryTree(2);
    bt.right = new BinaryTree(2);
    bt.left.right = new BinaryTree(3);
    bt.right.right = new BinaryTree(3);
    //bt=BinaryTree.buildATree(bt, array);
    System.out.print(isSymmetric(bt));
    BinaryTree.inOrderTraversal(bt);
}
public static boolean isSymmetric(BinaryTree root){
    if(root==null)
        return true;
    return isSymmetricLR(root.left,root.right);
}
public static boolean isSymmetricLR(BinaryTree left, BinaryTree right){
    if(left == null && right == null)
        return true;
    if(left!=null && right!=null)
        return (left.data == right.data) &&
                (isSymmetricLR(left.left, right.right)) &&
                (isSymmetricLR(left.right, right.left));
    return false;
}

}

Answer 10

EDITAR

Como se señaló en los comentarios, mi primera versión del algoritmo falló para ciertas entradas. No voy a reinventar la rueda, solo proporcionaré una respuesta de Python usando el algoritmo correcto de @gvijay. Primero, una representación para el árbol binario:

class BTree(object):
    def __init__(self, l, r, v):
        self.left  = l
        self.right = r
        self.value = v
    def is_mirror(self):
        return self._mirror_equals(self.left, self.right)
    def _mirror_equals(self, left, right):
        if left is None or right is None:
            return left is None and right is None
        return (left.value == right.value
                and self._mirror_equals(left.left, right.right)
                and self._mirror_equals(left.right, right.left))

Probé el código anterior utilizando todos los árboles de muestra en la pregunta y los árboles que devolvían resultados incorrectos, como se menciona en los comentarios. Ahora los resultados son correctos para todos los casos:

root1 = BTree(
    BTree(None, None, 2),
    BTree(None, None, 2),
    1)
root1.is_mirror() # True

root2 = BTree(
    BTree(None, BTree(None, None, 3), 2),
    BTree(None, None, 2),
    1)
root2.is_mirror() # False

root3 = BTree(
    BTree(
        BTree(None, None, 4),
        BTree(None, None, 3),
        2),
    BTree(
        BTree(None, None, 3),
        BTree(None, None, 4),
        2),
    1)
root3.is_mirror() # True

root4 = BTree(
    BTree(
        BTree(None, None, 3),
        BTree(None, None, 4),
        2),
    BTree(
        BTree(None, None, 3),
        BTree(None, None, 4),
        2),
    1)
root4.is_mirror() # False

root5 = BTree(
    BTree(BTree(None, None, 3), None, 2),
    BTree(None, BTree(None, None, 3), 2),
    1)
root5.is_mirror() # True

root6 = BTree(BTree(None, None, 1), None, 1)
root6.is_mirror() # False

root7 = BTree(BTree(BTree(None, None, 1), None, 2), None, 1)
root7.is_mirror() # False

Answer 11

Solución 1 - Recursivamente:

bool isMirror(BinaryTreeNode *a, BinaryTreeNode *b)
{
    return (a && b) ?  
        (a->m_nValue==b->m_nValue 
        && isMirror(a->m_pLeft,b->m_pRight) 
        && isMirror(a->m_pRight,b->m_pLeft)) :  
    (a == b);
}
bool isMirrorItselfRecursively(BinaryTreeNode *root) 
{
    if (!root)
        return true;

    return isMirror(root->m_pLeft, root->m_pRight);
}

Solución 2 - iterativamente:

bool isMirrorItselfIteratively(BinaryTreeNode *root) 
{
    /// use single queue
    if(!root) return true;
    queue<BinaryTreeNode *> q;
    q.push(root->m_pLeft);
    q.push(root->m_pRight);
    BinaryTreeNode *l, *r;
    while(!q.empty()) {
        l = q.front();
        q.pop();
        r = q.front();
        q.pop();
        if(l==NULL && r==NULL) continue;
        if(l==NULL || r==NULL || l->m_nValue!=r->m_nValue) return false;
        q.push(l->m_pLeft);
        q.push(r->m_pRight);
        q.push(l->m_pRight);
        q.push(r->m_pLeft);
    }

    return true;
}

Answer 12

Soluciones recursivas e iterativas en Java usando los enfoques discutidos anteriormente

Recursivo

public Boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }

    return isSymmetricInternal(root.left, root.right);
}

private Boolean isSymmetricInternal(TreeNode leftNode,
        TreeNode rightNode) {

    boolean result = false;

    // If both null then true
    if (leftNode == null && rightNode == null) {
        result = true;
    }

    if (leftNode != null && rightNode != null) {
        result = (leftNode.data == rightNode.data)
                && isSymmetricInternal(leftNode.left, rightNode.right)
                && isSymmetricInternal(leftNode.right, rightNode.left);
    }

    return result;
}

Iterativo utilizando LinkedList como cola

private Boolean isSymmetricRecursive(TreeNode root) {
    boolean result = false;

    if (root == null) {
        return= true;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root.left);
    queue.offer(root.right);

    while (!queue.isEmpty()) {
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();

        if (left == null && right == null) {

            result = true;

        }
        else if (left == null || 
                right == null || 
                left.data != right.data) {
            // It is required to set result = false here
            result = false;
            break;
        }

        else if (left != null && right != null) {
            queue.offer(left.left);
            queue.offer(right.right);

            queue.offer(left.right);
            queue.offer(right.left);
        }
    }

    return result;
}

Caso de prueba

    @Test
public void testTree() {

    TreeNode root0 = new TreeNode(1);
    assertTrue(isSymmetric(root0));
    assertTrue(isSymmetricRecursive(root0));

    TreeNode root1 = new TreeNode(1, new TreeNode(2), new TreeNode(2));
    assertTrue(isSymmetric(root1));
    assertTrue(isSymmetricRecursive(root1));

    TreeNode root2 = new TreeNode(1,
            new TreeNode(2, null, new TreeNode(3)), new TreeNode(2));
    assertFalse(isSymmetric(root2));
    assertFalse(isSymmetricRecursive(root2));

    TreeNode root3 = new TreeNode(1, new TreeNode(2, new TreeNode(4),
            new TreeNode(3)), new TreeNode(2, new TreeNode(3),
            new TreeNode(4)));
    assertTrue(isTreeSymmetric(root3));
    assertTrue(isSymmetricRecursive(root3));

    TreeNode root4 = new TreeNode(1, new TreeNode(2, new TreeNode(3),
            new TreeNode(4)), new TreeNode(2, new TreeNode(3),
            new TreeNode(4)));
    assertFalse(isSymmetric(root4));
    assertFalse(isSymmetricRecursive(root4));
}

Clase de nodo de árbol

public class TreeNode {

int data;

public TreeNode left;
public TreeNode right;

public TreeNode(int data){
    this(data, null, null);
}

public TreeNode(int data, TreeNode left, TreeNode right)
{
    this.data = data;
    this.left = left;
    this.right = right;
}
}