剑指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


 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)