一、     题目

     给一个二叉树，推断这个树是不是镜像的（对称的）。

样例:     1   

         / \

       2   2

      / \   / \

    3   4 4  3

  可是这个就不是:     1

                                 / \

                               2   2

                               \     \

                               3     3

二、     分析

1、递归

     从根開始，迭代查看左子树和右子树是否是对称的。

    当中左子树和右子树对称的条件（均非空条件下）是：

   1>两个节点值相等

   2>左节点的左子树和右节点的右子树对称

   3>左节点的右子树和右节点的左子树对称

2、非递归

    使用非递归时，我们能够创建两个队列，将根节点的左右子树分别入队，入队的同一时候比較。发现对称位置的节点值不等。则返回false;

   1>  根节点的左右子树入队

   2>  队列出队

   3>  假设值相等，则4，否则返回false

   4>  将当前左节点左子树和当前右节点的右子树入队。假设当中仅仅要有一个为空，则返回false

   5>  将当前右节点左子树和当前左节点的右子树入队。假设当中仅仅要有一个为空，则返回false

   6>  最后，推断两个队列是否同一时候为空，是。则返回true,否则返回false

递归:

/** * 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 *Lroot,TreeNode *Rroot) {        if(Lroot==NULL)        	return Rroot==NULL;                else {        	if(Rroot==NULL)        		return false;        	if(Lroot->val!=Rroot->val)        		return false;            	if(!isSymmetric(Lroot->right,Rroot->left))        		return false;        	if(!isSymmetric(Lroot->left,Rroot->right))        		return false;        	return true;        }	}    bool isSymmetric(TreeNode *root) {        if(root==NULL) return true;        TreeNode *Rroot;        TreeNode *Lroot;        Rroot = root->right;        Lroot = root->left;		return isSymmetric(Lroot,Rroot);     		    }};

/** * 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) return true;        return compare(root->left, root->right);    }    bool compare(TreeNode *Lroot, TreeNode *Rroot) {        if (Lroot!=NULL && Rroot!=NULL) return true;        if (Lroot!=NULL && Rroot==NULL || Lroot==NULL && Rroot!=NULL) return false;        if (Lroot->val != Rroot->val) return false;        return compare(Lroot->left, Rroot->right) && compare(Lroot->right, Rroot->left);    }};

非递归:

/** * 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;        queue
     
       Lque;        queue
      
        Rque;        if(root->left) Lque.push(root->left);        if(root->right) Rque.push(root->right);        while(!Lque.empty()&&!Rque.empty()){        	TreeNode *ql = Lque.front();        	TreeNode *qr = Rque.front();        	Lque.pop();        	Rque.pop();        	if(ql->val == qr->val){        		if(ql->left&&qr->right){        			Lque.push(ql->left);        			Rque.push(qr->right);        		}        		else if(ql->left||qr->right)        			return false;        		if(qr->left&&ql->right){        			Lque.push(qr->left);        			Rque.push(ql->right);        		}        		else if(qr->left||ql->right)        			return false;        	}        	else return false;        }        if(Lque.empty() && Rque.empty())        	return true;        else             return false;    }};