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


 



 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)