剑指offer之中判断二叉树是不是对称二叉树（递归和非递归实现）
【摘要】 1 问题
判断二叉树是不是对称（递归和非递归实现）
如下二叉树，就是对称的二叉树
2 3 3 1 4 4 1
如下二叉树，就是非对称的二叉树
2 3 3 1 4 4 2
2 代码实现
#include <iostream>#inclu...
1 问题
判断二叉树是不是对称（递归和非递归实现）
如下二叉树，就是对称的二叉树
-
2
-
3 3
-
1 4 4 1
如下二叉树，就是非对称的二叉树
-
2
-
3 3
-
1 4 4 2
2 代码实现
-
#include <iostream>
-
#include <queue>
-
-
using namespace std;
-
-
#define true 1
-
#define false 0
-
-
typedef struct Node
-
{
-
int value;
-
struct Node* left;
-
struct Node* right;
-
} Node;
-
-
int isSymmetricTree(Node *head);
-
int isSymmetric(Node *left, Node *right);
-
int isSymmetricTree1(Node *head);
-
-
/*
-
*判断是否是对称二叉树（递归实现）
-
*/
-
int isSymmetricTree(Node *head)
-
{
-
if (head == NULL)
-
{
-
return true;
-
}
-
return isSymmetric(head, head);
-
}
-
-
int isSymmetric(Node *left, Node *right)
-
{
-
if (left == NULL && right == NULL)
-
{
-
return true;
-
}
-
if (left == NULL || right == NULL)
-
{
-
return false;
-
}
-
if (left->value != right->value)
-
{
-
return false;
-
}
-
return isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
-
}
-
-
/*
-
*判断是否是对称二叉树（非递归实现）
-
*/
-
int isSymmetricTree1(Node *head)
-
{
-
if (head == NULL)
-
{
-
return true;
-
}
-
std::queue<Node *> queue1;
-
std::queue<Node *> queue2;
-
queue1.push(head->left);
-
queue2.push(head->right);
-
while(!queue1.empty() || !queue2.empty())
-
{
-
Node *left = queue1.front();
-
Node *right = queue2.front();
-
-
if ((left != NULL) && (right == NULL))
-
{
-
return false;
-
}
-
if ((left == NULL) && (right != NULL))
-
{
-
return false;
-
}
-
//因为上面情况只包含left为NULL和right不为NULL以及left不为NULL和right为NULL，
-
//还包含2种情况，left和right都为NULL,以及left和right都不为NULL,所以我们left->value和right->判断相等的时候
-
//一定要记得对left和right都不是NULL的前提下才能调用->,下次切记，看到指针->的时候需要判断指针是否为NULL
-
//left和right都为NULL的时候，我们直接对queue1和queue2进行pop()操作
-
if (left && right && (left->value != right->value))
-
{
-
return false;
-
}
-
-
queue1.pop();
-
queue2.pop();
-
-
if (left != NULL)
-
{
-
queue1.push(left->left);
-
queue1.push(left->right);
-
}
-
if (right != NULL)
-
{
-
queue2.push(right->right);
-
queue2.push(right->left);
-
}
-
}
-
return true;
-
}
-
-
int main()
-
{
-
/* 2
-
* 3 3
-
* 1 4 4 1
-
*
-
*/
-
Node head1, node1, node2, node3, node4, node5, node6;
-
Node head2, node7, node8;
-
head1.value = 2;
-
node1.value = 3;
-
node2.value = 3;
-
node3.value = 1;
-
node4.value = 4;
-
node5.value = 4;
-
node6.value = 1;
-
-
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;
-
-
if (isSymmetricTree(&head1))
-
{
-
std::cout << "tree is symmertric" << std::endl;
-
}
-
else
-
{
-
std::cout << "tree is not symmertric" << std::endl;
-
}
-
if (isSymmetricTree1(&head1))
-
{
-
std::cout << "tree is symmertric" << std::endl;
-
}
-
else
-
{
-
std::cout << "tree is not symmertric" << std::endl;
-
}
-
-
return 0;
-
}
-
-
3 运行结果
-
tree is symmertric
-
tree is symmertric
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/90683562
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）