5/31刷题

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==nullptr) return true;
        bool result=isSymmetric1(root->left,root->right);
        return result;

    }
    bool isSymmetric1(TreeNode* p1,TreeNode* p2)
    {
        if(p1==nullptr&&p2==nullptr) return true;//都为空，返回true
        if(p1==nullptr||p2==nullptr) return false;//有一个为空，返回false
        if(p1->val!=p2->val)
        {
            return false;//不相等直接退出
        }
        return isSymmetric1(p1->left,p2->right)&&isSymmetric1(p1->right,p2->left);//左右子树做对比
    }
};

思路二：迭代

class Solution {
public:
    bool check(TreeNode *u, TreeNode *v) {
        queue <TreeNode*> q;
        q.push(u); q.push(v);
        while (!q.empty()) {
            u = q.front(); q.pop();
            v = q.front(); q.pop();
            if (!u && !v) continue;//如果都为空，判断队列是否为空
            if ((!u || !v) || (u->val != v->val)) return false;//值不相等或有一个为空，返回false

            q.push(u->left); 
            q.push(v->right);

            q.push(u->right); 
            q.push(v->left);//按相反顺序插入
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};