LeetCode 101. 对称二叉树（递归&循环）

Michael阿明

发布于 2020-07-13 15:28:14

3980

1. 题目

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/symmetric-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 递归

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return sym(root,root);
    }
    bool sym(TreeNode *t1, TreeNode *t2)
    {
    	if((!t1&&t2)||(t1&&!t2))
    		return false;
    	else if(!t1&&!t2)
    		return true;
    	else
    		return(t1->val==t2->val && sym(t1->left,t2->right)
    				&& sym(t1->right,t2->left));
    }
};

2.2 循环

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        TreeNode *t1, *t2;
        queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        while(!q.empty())
        {
        	t1 = q.front();
        	q.pop();
        	t2 = q.front();
        	q.pop();
        	if((!t1&&t2)||(t1&&!t2))
    			return false;
    		else if(!t1&&!t2)
    			continue;
    		else//t1,t2都存在
    		{
    			if(t1->val != t2->val)
    				return false;
    			q.push(t1->left);
    			q.push(t2->right);
    			q.push(t1->right);
    			q.push(t2->left);
    		}
        }
        return true;
    }
};

《剑指Offer》同题：面试题28. 对称的二叉树

递归

class Solution {
	bool ans = true;
public:
    bool isSymmetric(TreeNode* root) {
        dfs(root,root);
        return ans;
    }

    void dfs(TreeNode* r1, TreeNode* r2)
    {
    	if(!ans || (!r1 && !r2))
    		return;
    	if((!r1 && r2)||(r1 && !r2))
    	{
    		ans = false;
    		return;
    	}
    	if(r1->val != r2->val)
    		ans = false;
    	dfs(r1->left,r2->right);
    	dfs(r1->right,r2->left);
    }
};

循环

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        TreeNode *r1, *r2;
        while(!q.empty())
        {
        	r1 = q.front();	q.pop();
        	r2 = q.front();	q.pop();
        	if((!r1 && r2)||(r1 && !r2))
        		return false;
        	if(r1 && r2)
        	{
        		if(r1->val != r2->val)
        			return false;
        		q.push(r1->left);
        		q.push(r2->right);
        		q.push(r1->right);
        		q.push(r2->left);
        	}
        }
        return true;
    }
};