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