# Symmetric Tree

> Given a binary tree, check whether it is a mirror of itself(ie, symmetric around its center)

> For example, this tree is symmetric:

```
1
/ \
2 2
/ \ / \
3 4 4 3
```
> But the following tree is not.

```
1
/ \
2 2
\ \
3 3
```

1. 左右两个节点的大小是否相同.
2. 左节点的左孩子是否和右节点的右孩子相同.
3. 左节点的右孩子是否和右节点的左孩子相同.

```c++
/**
* Definition for binary tree
* 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 Helper(root->left,root->right);
}

bool Helper(TreeNode* left, TreeNode* right)
{
if(left == NULL&&right == NULL)
return true;
else if(left == NULL||right == NULL)
return false;
bool cond1 = left->val == right->val;
bool cond2 = Helper(left->left,right->right);
bool cond3 = Helper(left->right, right->left);
return cond1&&cond2&&cond3;
}

};
```

```c++

/**
* Definition for binary tree
* 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;
TreeNode* n1 = root->left;
TreeNode* n2 = root->right;
if(!n1&&!n2)
return true;
if((!n1&&n2)||(n1&&!n2))
return false;
queue Q1;
queue Q2;
Q1.push(n1);
Q2.push(n2);
while(!Q1.empty() && !Q2.empty())
{
TreeNode* tmp1 = Q1.front();
TreeNode* tmp2 = Q2.front();
Q1.pop();
Q2.pop();
if((!tmp1&&tmp2) || (tmp1&&!tmp2))
return false;
if(tmp1&&tmp2)
{
if(tmp1->val != tmp2->val)
return false;
Q1.push(tmp1->left);
Q1.push(tmp1->right); //note: this line we should put the mirror sequence in two queues
Q2.push(tmp2->right);
Q2.push(tmp2->left);
}
}
return true;
}
};
```