在线午夜精品自拍小视频_无码av无码专区线_亚洲无码精品人妻_人人澡欧美一区

劍指offer之中判斷二叉樹是不是對稱二叉樹（遞歸和非遞歸實現(xiàn)）

1 問題

判斷二叉樹是不是對稱（遞歸和非遞歸實現(xiàn)）

如下二叉樹，就是對稱的二叉樹

                  2
                   3     3           
                 1  4   4  1

如下二叉樹，就是非對稱的二叉樹

                  2
                   3     3           
                 1  4   4  2

2 代碼實現(xiàn)

    #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);
     
    /*
     *判斷是否是對稱二叉樹（遞歸實現(xiàn)）
     */
    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);
    }
     
    /*
     *判斷是否是對稱二叉樹（非遞歸實現(xiàn)）
     */
    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以及l(fā)eft不為NULL和right為NULL，
            //還包含2種情況，left和right都為NULL,以及l(fā)eft和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


 



 

作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學習,
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎入門進階人工智能(鏈接)