对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：最近一直在用队列，不假思索直接上

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
         deque<TreeNode*> s;//双端队列
        s.push_front(pRoot);
        while(!s.empty())
        {
            if(s.size()==1)//根节点单独拎出来
            {
                TreeNode* t = s.front();s.pop_front();
                if(t->left)s.push_back(t->left);//这里考虑左右子树存在的情况下才压入队列中，跟下面的情况有点不同，
                //下面是父节点存在的情况下，就把左右子树压入队列，这是因为考虑空间结构对称
                if(t->right)s.push_back(t->right);
                continue;
            }
            int size = s.size();
            int count = 0;
            //if(size%2==1) return false;
            vector<TreeNode*> temp(size);
            for(int i = 0;i<size;i++)
            {
                temp[i]=s[i];
            }
            while(count<size/2)//前后对比
            {
                TreeNode* t = s.front();s.pop_front();
                TreeNode* d = s.back();s.pop_back();
                if(t!=NULL&&d!=NULL&&t->val==d->val)//都不为null且值相等
                {
                }
                else if(t==NULL&&d==NULL)//都为NULL
                {
                }
                else 
                {
                    return false;
                }
                count++;
            }
            count = 0;
            while(count<size)
            {
                if(temp[count])s.push_back(temp[count]->left),s.push_back(temp[count]->right);//父节点存在，就把左右子树压入队列
                count++;
            }
        }
        return true;
    }
};

后来想了想，可以去掉辅助vector，下一版本

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:    
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
         deque<TreeNode*> s;
        s.push_front(pRoot);
        while(!s.empty())
        {
            if(s.size()==1)
            {
                TreeNode* t = s.front();s.pop_front();
                if(t->left)s.push_back(t->left);
                if(t->right)s.push_back(t->right);
                continue;
            }
            int size = s.size();
            int count = 0;
            //if(size%2==1) return false;
          //  vector<TreeNode*> temp(size);
         //   for(int i = 0;i<size;i++)
          //  {
          //      temp[i]=s[i];
          //  }
            while(count<size/2)
            {
                //TreeNode* t = s.front();s.pop_front();
                //TreeNode* d = s.back();s.pop_back();
                TreeNode* t = s[count];//通过下标访问
                TreeNode* d = s[size-1-count];
                if(t!=NULL&&d!=NULL&&t->val==d->val)
                {
                }
                else if(t==NULL&&d==NULL)
                {
                }
                else 
                {
                    return false;
                }
                count++;
            }
              count = 0;
            while(count<size)
            {
               // if(temp[count])s.push_back(temp[count]->left),s.push_back(temp[count]->right);
              //  count++;
                 TreeNode* t = s.front();s.pop_front();
                if(t) s.push_back(t->left),s.push_back(t->right);
                count++;
            }
        }
        return true;
    }
};

接着试试递归写法,思路也很简单，比较根节点的左右子树，接着递归比较左子树的左子树和右子树的右子树，左子树的右子树和右子树的左子树，就是这个思路，递归就行了，结束条件，全部符合条件返回true，否则返回false；

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    bool compare(TreeNode* left,TreeNode* right)
    {
        if(left==NULL) return right==NULL;
        if(right==NULL) return false;
        if(left->val!=right->val) return false;
        return compare(left->left,right->right)&&compare(left->right,right->left);
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
         return compare(pRoot->left,pRoot->right);
    }
};