剑指offer之二叉树的镜像

1题目

求二叉树A的镜像,就是对称图,比如下面的树B是树A的镜像
比如:
              2                           2
   树A  3    5      树B        5     3
        1  4  2  3              3   2  4  1

2 代码实现

#include <stdio.h>

#define true 1
#define false 0

typedef struct Node
{
    int value;
    struct Node* left;
    struct Node* right;
} Node;

void reverse_tree(Node *head)
{
   if (head != NULL)
   {
       Node *temp = head->left;
       head->left = head->right;
       head->right = temp;
       reverse_tree(head->left);
       reverse_tree(head->right);
   }
}
void reverse_tree1(Node *head)
{
   if (head == NULL)
   {
      return;
   }
   if (head->left == NULL && head->right == NULL)
   {
      return;
   }
   Node *temp = head->left;
   head->left = head->right;
   head->right = temp;
   //if (head->left != NULL)
        reverse_tree(head->left);
   //if (head->right != NULL)
        reverse_tree(head->right);
}

void printf_tree(Node *head)
{
    if (head != NULL)
    {
        printf("val is: %d\n", head->value);
        printf_tree(head->left);
        printf_tree(head->right);
    }
}

int main()
{
    /*              2
     *           3    5            5
     *         1  4  2  3        2   3
     *
     */
    Node head1, node1, node2, node3, node4, node5, node6;
    Node head2, node7, node8;
    head1.value = 2;
    node1.value = 3;
    node2.value = 5;
    node3.value = 1;
    node4.value = 4;
    node5.value = 2;
    node6.value = 3;

    head1.left = &node1;
    head1.right = &node2;

    node1.left = &node3;
    node1.right = &node4;

    node2.left = &node5;
    node2.right = &node6;

    node3.left = NULL;
    node3.right = NULL;
    node4.left = NULL;
    node4.right = NULL;
    node5.left = NULL;
    node5.right = NULL;
    node6.left = NULL;
    node6.right = NULL;

    head2.value = 5;
    node7.value = 2;
    node8.value = 3;

    head2.left = &node7;
    head2.right = &node8;
    node7.left = NULL;
    node7.right = NULL;
    node8.left = NULL;
    node8.right = NULL;

    printf_tree(&head1);
    printf("----\n");
    reverse_tree(&head1);
    printf_tree(&head1);
}

3 运行结果

val is: 2
val is: 3
val is: 1
val is: 4
val is: 5
val is: 2
val is: 3
----
val is: 2
val is: 5
val is: 3
val is: 2
val is: 3
val is: 4
val is: 1
(0)

相关推荐