# 对称二叉树

<p>给定一个二叉树，检查它是否是镜像对称的。</p>

<p>&nbsp;</p>

<p>例如，二叉树&nbsp;<code>[1,2,2,3,4,4,3]</code> 是对称的。</p>

<pre>    1
   / \
  2   2
 / \ / \
3  4 4  3
</pre>

<p>&nbsp;</p>

<p>但是下面这个&nbsp;<code>[1,2,2,null,3,null,3]</code> 则不是镜像对称的:</p>

<pre>    1
   / \
  2   2
   \   \
   3    3
</pre>

<p>&nbsp;</p>

<p><strong>进阶：</strong></p>

<p>你可以运用递归和迭代两种方法解决这个问题吗？</p>

<p>以下<font color="red">错误</font>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
```
### after

```cpp

```

## 答案

```cpp
class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        if (!root)
            return true;
        queue<TreeNode *> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty())
        {
            auto p1 = q.front();
            q.pop();
            auto p2 = q.front();
            q.pop();
            if (!p1 && !p2)
                continue;
            if (!p1 || !p2)
                return false;
            if (p1->val != p2->val)
                return false;
            q.push(p1->right);
            q.push(p1->left);
            q.push(p2->right);
            q.push(p2->left);
        }
        return true;
    }
};

```
## 选项

### A
```cpp
class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        queue<TreeNode *> q1, q2;
        if (!root)
            return true;
        q1.push(root->left);
        q2.push(root->right);
        while (!q1.empty() && !q2.empty())
        {
            TreeNode *node1 = q1.front();
            q1.pop();
            TreeNode *node2 = q2.front();
            q2.pop();
            if (!node1 && !node2)
                continue;
            if ((!node1 && node2) || (node1 && !node2) || (node1->val != node2->val))
                return false;
            q1.push(node1->left);
            q1.push(node1->right);
            q2.push(node2->right);
            q2.push(node2->left);
        }
        return true;
    }
};
```

### B
```cpp
class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        if (!root)
            return true;
        return helper(root->left, root->right);
    }
    bool helper(TreeNode *left, TreeNode *right)
    {
        if (!left && !right)
            return true;
        if ((!left && right) || (left && !right) || (left->val != right->val))
            return false;
        return helper(left->left, right->right) && helper(left->right, right->left);
    }
};
```

### C
```cpp
class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        return ismirror(root, root);
    }
    bool ismirror(TreeNode *t1, TreeNode *t2)
    {
        if (t1 == NULL && t2 == NULL)
            return true;
        if (t1 == NULL || t2 == NULL)
            return false;
        return (t1->val == t2->val) && ismirror(t1->left, t2->right) && ismirror(t1->right, t2->left);
    }
};
```
