leetcode 101. 对称二叉树(C++)

r囧r小猫 2023-07-17 06:49 40阅读 0赞

### 文章目录 ###

*  题目
 *  递归法
 *  迭代法

# 题目 #

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

例如，二叉树 \[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

说明:  
如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

# 递归法 #

*  如果一个树的左子树与右子树镜像对称，那么这个树是对称的。

代码如下：

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

结果：  
![在这里插入图片描述][20200320222533968.png]

# 迭代法 #

*  类似于树的层次遍历，不过需改变节点加入队列的顺序  
    通过对比两个连续的节点是否一样来判断其是否镜像对称

代码如下：

class Solution { 
    public:
        bool isSymmetric(TreeNode* root) { 
            queue<TreeNode*> q;
    		q.push(root);
    		q.push(root);
    		while (!q.empty())
    		{ 
    			auto t1 = q.front();
    			q.pop();
    			auto t2 = q.front();
    			q.pop();
    			if (!t1 && !t2) continue;
    			if (!t1 || !t2)
    				return false;
    			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;
        }
    };

结果：  
![在这里插入图片描述][20200320230312490.png]

[20200320222533968.png]: /images/20230528/33f6a7af8a2f4e79bf07e662b1bb069a.png
[20200320230312490.png]: /images/20230528/f960518550a243f3aee31ebb1ebb6755.png