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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

		    1/ \2   2/ \ / \3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

		   1/ \2   2\   \3    3

<方法1>递归实现

#include<iostream>
#include<queue>
using namespace std;struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};
bool _isSymmetric(struct TreeNode *t1, struct TreeNode *t2)
{if (t1 == NULL && t2 == NULL)return true;if (t1 == NULL || t2 == NULL)return false;return t1->val == t2->val &&  _isSymmetric(t1->left, t2->right) && _isSymmetric(t1->right, t2->left);
}
bool isSymmetric(struct TreeNode* root)
{if (root == NULL)return true;return _isSymmetric(root->left, root->right);
}

<方法2> 队列实现

#include<iostream>
#include<queue>
using namespace std;struct TreeNode 
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:bool _isSymmetric(struct TreeNode* t1, struct TreeNode* t2){queue <TreeNode*> q;q.push(t1), q.push(t2);while (!q.empty()){t1 = q.front();q.pop();t2 = q.front();q.pop();if (!t1 && !t2)continue;if ((!t1 || !t2) || (t1->val != t2->val))return false;q.push(t1->left);q.push(t2->right);q.push(t1->right);q.push(t2->left);}return true;}bool isSymmetric(struct TreeNode* root){if (root == NULL)return true;return _isSymmetric(root, root);}
};