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.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

1  / \ 2   3    /   4    \     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

Solution 1: 递归，left对应right，left->left对应right->right，left->right对应right->left

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     bool isSymmetric(TreeNode* root) {13         if(!root)return true;14         return isSymTree(root->left,root->right);15     }16     bool isSymTree(TreeNode *p,TreeNode *q){17         if(!isSameNode(p,q))18             return false;19         else if(!p&&!q)20             return true;21         else22             return isSymTree(p->left,q->right) && isSymTree(p->right,q->left);23     }24     bool isSameNode(TreeNode *p,TreeNode *q){25         if(!p&&!q)      //必需加上这个判断条件，否则若p、q为空下面的->val会运行时错误26             return true;27         else if((!p&&q)||(p&&!q)||(p->val!=q->val))     //利用||的短路效应避免运行时错误28             return false;29         return true;30     }31 };

Solution 2 :非递归，待续