一.题目：对称二叉树

2.算法思想

 （1）（递归）

对称的条件：
1.根结点相同
2. r1树的左子树同r2树的右子树，r1树的右子树同r2树的左子树。
所以可以用递归实现，注意结构体指针引用元素要用->而不能用小点

 （2）（迭代）

用队列迭代，当队列中每两个连续的结点都是相同值时则互为镜像。该队列的处理：每次提取子树左结点A和右结点B和然后比较，然后将A结点的左结点和B结点的右结点插入队列，将A结点的右结点和B结点的左结点插入队列，直至比较到队列为空位置。

3.代码

（1）递归版本

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for a binary tree node.
     
    
   

    

     

    
    

     

       * struct TreeNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * TreeNode *left;
     
    
   

    

     

    
    

     

       * TreeNode *right;
     
    
   

    

     

    
    

     

       * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     
    
   

    

     

    
    

     

       * };
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    bool isSymmetric(TreeNode* root) {
     
    
   

    

     

    
    

     
        if(root==NULL) return true;
     
    
   

    

     

    
    

     
        return isSym(root->left,root->right);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    //判断根结点为r1和r2的两棵树是否是对称的
     
    
   

    

     

    
    

     
    bool isSym(TreeNode* r1,TreeNode* r2){
     
    
   

    

     

    
    

     
        if(r1==NULL&&r2==NULL) return true;//能通过第一行则说明两者都不是空
     
    
   

    

     

    
    

     
        if(r1==NULL||r2==NULL) return false;
     
    
   

    

     

    
    

     
        //对称的条件：
     
    
   

    

     

    
    

     
        //1.根结点相同 2.1树的左子树同2树的右子树(右同)
     
    
   

    

     

    
    

     
        return r1->val==r2->val && isSym(r1->left,r2->right)&&isSym(r1->right,r2->left);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

（2）迭代版本

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
    bool isSymmetric(TreeNode* root) {
     
    
   

    

     

    
    

     

              std::queue<TreeNode*> q;
     
    
   

    

     

    
    

     

              q.push(root);
     
    
   

    

     

    
    

     

              q.push(root);
     
    
   

    

     

    
    

     
        while(!q.empty())//队列空则结束循环
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  TreeNode* t1 = q.front();
     
    
   

    

     

    
    

     

                  q.pop();
     
    
   

    

     

    
    

     

                  TreeNode* t2 = q.front();
     
    
   

    

     

    
    

     

                  q.pop();
     
    
   

    

     

    
    

     
            if(t1==NULL && t2==NULL)
     
    
   

    

     

    
    

     
                continue;//continue跳过这一轮
     
    
   

    

     

    
    

     
            if(t1==NULL || t2==NULL)
     
    
   

    

     

    
    

     
                return false;//一个空一个不空则结束这层递归
     
    
   

    

     

    
    

     
            if(t1->val != t2->val)
     
    
   

    

     

    
    

     
                return false;//此时队列中相邻的两个元素不同则return
     
    
   

    

     

    
    

     

                  q.push(t1->left);
     
    
   

    

     

    
    

     

                  q.push(t2->right);
     
    
   

    

     

    
    

     

                  q.push(t1->right);
     
    
   

    

     

    
    

     

                  q.push(t2->left);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return true;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      };
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/104382984