Зеркальное изображение бинарного дерева

Question

Предположим, есть дерево:

             1
            / \
           2   3
              / \
             4   5

Тогда зеркальное отображение будет:

              1
             / \
            3   2
           / \
          5   4

Предположим, что узлы имеют следующую структуру:

struct node{
      node left;
      node right;
      int value;
}

Может кто-нибудь предложить алгоритм для этого?

Answer 1

struct node *MirrorOfBinaryTree( struct node *root)
{ struct node *temp;
if(root)
{
MirrorOfBinaryTree(root->left);
MirrorOfBinaryTree(root->right);
/*swap the pointers in this node*/
temp=root->right;
root->right=root->left;;
root->left=temp;
}
return root;
}

Сложность времени: O (n) Сложность пространства: O (n)

Answer 2

рекурсивный код Java

public class TreeMirrorImageCreator {

public static Node createMirrorImage(Node originalNode,Node mirroredNode){

    mirroredNode.setValue(originalNode.getValue());

    if(originalNode.getLeft() != null){
        mirroredNode.setLeft(createMirrorImage(originalNode.getRight(),new Node(0)));
    }

    if(originalNode.getRight() != null){
        mirroredNode.setRight(createMirrorImage(originalNode.getLeft(), new Node(0)));
    }

    return mirroredNode;

}
}

Answer 3

Вот моя функция.Предложите, если есть лучшее решение:

void mirrorimage(struct node *p)
{
    struct node *q;
    if(p!=NULL)
    {
        q=swaptrs(&p);
        p=q;
        mirrorimage(p->left);
        mirrorimage(p->right);
    }
}

struct node* swaptrs(struct node **p)
{
    struct node *temp;
    temp=(*p)->left;
    (*p)->left=(*p)->right;
    (*p)->right=temp;
    return (*p);
}