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