剑指offer之中判断二叉树是不是对称二叉树（递归和非递归实现）

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