leetcode:Symmetric Tree

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;
    }
};