leetcode:Symmetric Tree

一、 题目

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

例子: 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; } };