Miroir Image d'un arbre n-aire? Quelqu'un peut-il expliquer?

Question

Cette question a été posée lors d'une interview d'Amazon. J'ai essayé de trouver une solution mais je n'ai pas eu la solution. Tout le monde peut résoudre le problème avec les détails.

Answer 1

Ceci est une question d'entrevue assez standard. Pensez à la question de cette façon, si vous vous teniez devant un miroir avec votre arbre à quoi cela ressemblerait-il. Je vous encourage à dessiner un arbre simple et à vous tenir devant le miroir pour dessiner ce à quoi il ressemble. Après avoir fait cela, vous avez peut-être réalisé que cette question est presque identique à l'inversion d'une arborescence. Le processus d'inversion est, à chaque niveau, permuter les nœuds gauche et droit, et continuer à traverser si et seulement si le nœud enfant existe.

Voici quelques pseudocode pour vous aider à démarrer:

invert_bst(bst): 
    bst's left node = bst's right node 
    if bst's left child is not null: 
     invert_bst(bst left child) 
    if bst's right child is not null: 
     invert_bst(bst right child) 

J'encourage vivement à essayer de mettre en œuvre cette solution.

Bonne chance dans vos futures interviews!

Answer 2

C'est assez simple, l'image miroir signifie que le nœud gauche du nœud d'origine devient le nœud droit de l'arborescence de l'image miroir. Vous pouvez utiliser la traversée pré-commande et continuer à ajouter le noeud gauche pour l'original à droite pour le miroir et droite pour l'original à gauche pour le miroir.

public Node createTreeMirror(Node root) { 
    if (root == null) { 
     return null; 
    } 
    Node mirror = new Node(root.data); 
    mirror.right = createTreeMirror(root.left); 
    mirror.left = createTreeMirror(root.right); 
    return mirror; 
}