题目：
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1 / \ 2 2 / \ / \3 4 4 3
But the following is not:
1 / \ 2 2 \ \ 3 3
Note:Bonus points if you could solve it both recursively and iteratively.
思路分析：
题目要求分别用递归和迭代的方法进行。递归这里不说了，直接看代码。迭代算法可以使用C++标准库中的deque数据结构，允许从前面和后面操作元素。
递归算法：
class Solution{private:bool checkSymmetric(TreeNode *left, TreeNode *right){if (left == NULL && right == NULL){return true;}else if (left && right && left->val == right->val){return checkSymmetric(left->left, right->right) && checkSymmetric(left->right, right->left);}else{return false;}}public:bool isSymmetric(TreeNode *root){if (root == NULL){return true;}else{return checkSymmetric(root->left, root->right);}}};
迭代算法（使用deque结构）：
class Solution{public:bool isSymmetric(TreeNode *root){if (!root){return true;}//如果左右子树都为NULLif (!root->left && !root->right){return true;}//左右子树一个为NULL一个不为NULLif ((root->left && !root->right) || (!root->left && root->right)){return false;}//左右子树都不为NULLTreeNode *leftNode, *rightNode;deque<TreeNode*> nodeDeque;nodeDeque.push_front(root->left);nodeDeque.push_back(root->right);while (!nodeDeque.empty()){leftNode = nodeDeque.front();rightNode = nodeDeque.back();nodeDeque.pop_front();nodeDeque.pop_back();if (leftNode->val != rightNode->val){return false;}if ((leftNode->left && !rightNode->right) || (!leftNode->left && rightNode->right)){return false;}if (leftNode->left){nodeDeque.push_front(leftNode->left);nodeDeque.push_back(rightNode->right);}if ((leftNode->right && !rightNode->left) || (!leftNode->right && rightNode->left)){return false;}if (leftNode->right){nodeDeque.push_front(leftNode->right);nodeDeque.push_back(rightNode->left);}}return true;}};我看了下，使用递归算法在Leetcode上提交是8ms，使用迭代算法是10ms。
网上有的说采用中序遍历，，判断遍历的结果对称就OK了。实际上这是不行的。
class Solution{private:void inOrder(TreeNode *node, vector<int> &result){if (node){inOrder(node->left, result);result.push_back(node->val);inOrder(node->right, result);}}public:bool isSymmetric(TreeNode *root){if (root == NULL){return true;}vector<int> result;inOrder(root, result);vector<int>::size_type size = result.size();bool flag = true;for (int i = 0, j = size – 1; i < j; i++, j–){if (result[i] != result[j]){flag = false;break;}}return flag;}};这样的程序在比如{1， 2， 3， 3，#， 2}这样的测试用例就不能通过。
背着背包的路上，看过许多人，听过许多故事，
