C++ LeetCode 101 对称二叉树

递归

p->left对应q->right，保证镜像对称关系。

/**
 * 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 check(TreeNode* p,TreeNode* q)
    {
        if(!p&&!q)
            return true;
         else if(!p||!q)
            return false;
        return p->val==q->val&&check(p->left,q->right)&&check(p->right,q->left);
    }
    bool isSymmetric(TreeNode* root) {
        TreeNode *p,*q;
        if(root==NULL)
            return true;
        p=root->left;
        q=root->right;
        if(!p&&!q)
            return true;
        else if(!p||!q||p->val!=q->val)
            return false;
        else 
            return check(p,q);
        
    }
};

迭代

队列中相邻的数一定是镜像对称的，不断pop，循环判断。

/**
 * 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) {
        TreeNode *p,*q;
        if(root==NULL)
            return true;
        p=root->left;
        q=root->right;
        if(!p&&!q)
            return true;
        else if(!p||!q||p->val!=q->val)
            return false;
        else 
        {
            TreeNode *u,*v;
            queue<TreeNode*> que;
            que.push(p);
            que.push(q);
            while(!que.empty())
            {
                u=que.front();
                que.pop();
                v=que.front();
                que.pop();
                if(!u&&!v)
                    continue;
                if(!u||!v||u->val!=v->val)
                    return false;
                que.push(u->left);
                que.push(v->right);

                que.push(u->right);
                que.push(v->left);
            }
            return true;
        }
    }
};