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.

confused what "{1,#,2,3}" means? 

code:

1 class Solution { 2  3 public: 4  5 bool isSymmetric(TreeNode *root) { 6     if(root == NULL) return true; 7  8     queue
     
       lf, rt; 9     lf.push(root->left);10     rt.push(root->right);11     TreeNode *l, *r;12     while(!lf.empty() && !rt.empty()) {13         l = lf.front(); r = rt.front();14         lf.pop(); rt.pop();15         if(l == NULL && r == NULL) continue;16         if(l == NULL || r == NULL) return false;17         if(l->val != r->val) return false;18         lf.push(l->left); lf.push(l->right);19         rt.push(r->right); rt.push(r->left);20     }21     if(lf.empty() && rt.empty()) return true;22     else return false;23 }24 };
     

递归解：

// Recursive solutionpublic class Solution {public boolean isSymmetric(TreeNode root) {    if (root == null) {        return true;    }    return helper(root.left, root.right);}private boolean helper(TreeNode a, TreeNode b) {    if (a == null && b == null) return true;    if (a == null || b == null) return false;    if (a.val != b.val) return false;    return helper(a.left, b.right) && helper(a.right, b.left);}}