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

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/89893731