Vérifier si un arbre binaire est une image miroir ou symétrique

Question

Quel est l'algorithme de base pour tester si un arbre est symétrique. Comme il s'agit d'un arbre binaire, je suppose qu'il s'agit d'une définition récursive de ce type.

La question formelle est ci-dessous :

Un arbre binaire est une image miroir de lui-même si ses sous-arbres gauche et droit sont des images miroir identiques, c'est-à-dire que l'arbre binaire est symétrique. Quelques exemples permettent d'expliquer ce principe.

  1
 / \
2   2

VRAI

   1
  / \
 2   2
  \
   3

FAUX

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

VRAI

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

FAUX

       1
     /   \
    2     2
   /       \
  3         3

VRAI

Dans un langage de programmation de votre choix, définissez une classe/C struct BTree et une méthode associée pour vérifier si l'arbre est une image miroir. Pour les langages typés statiquement, vous pouvez supposer que les valeurs des nœuds sont toutes des entiers.

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

Supposons que la racine de l'arbre soit suivie par l'appelant et que la fonction isMirror() soit invoquée sur elle.

De même, si vous définissez une classe, veillez à fournir un constructeur sans argument et des méthodes getter/setter si les éléments de données ne sont pas accessibles au public.

Answer 1

Que diriez-vous d'appeler mirrorEquals(Root.left, Root.right) sur la fonction suivante :-

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);
}

Il s'agit de comparer le sous-arbre de gauche et le sous-arbre de droite inversé, en traçant une ligne imaginaire d'inversion à travers Root.

Answer 2

Solution 1 - De manière récursive :

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);
}

Solution 2 - Itérativement :

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 3

Solutions récursives et itératives en Java en utilisant les approches mentionnées ci-dessus

Récursif

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;
}

Iterative en utilisant LinkedList en tant que File d'attente

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;
}

Cas de test

    @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));
}

Nœud d'arbre classe

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;
}
}

Answer 4

La solution récursive de @gvijay est très claire, et voici une solution itérative.

Inspectez chaque ligne de l'arbre de haut en bas et voyez si les valeurs sont un palindrome. Si elles le sont toutes, alors oui, c'est un miroir. Vous devrez implémenter un algorithme pour visiter chaque ligne et inclure les valeurs nulles pour les arbres épars. En pseudo-code :

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

L'astuce consiste à concevoir l'algorithme de manière à itérer les lignes d'un arbre en tenant compte du fait que les arbres épars doivent avoir des valeurs nulles comme supports de remplacement. Cette implémentation Java semble correcte :

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 5

EDITAR

Comme cela a été souligné dans les commentaires, ma première version de l'algorithme a échoué pour certaines entrées. Je ne vais pas réinventer la roue, je vais simplement fournir une réponse en Python en utilisant l'algorithme correct de @gvijay. Tout d'abord, une représentation de l'arbre binaire :

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))

J'ai testé le code ci-dessus en utilisant tous les arbres échantillons dans la question y les arbres qui retournaient des résultats incorrects, comme mentionné dans les commentaires. Maintenant les résultats sont corrects dans tous les cas :

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