写在前面
本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……
专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：
- Tag：介绍本题牵涉到的知识点、数据结构；
- 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
- 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
- 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
- 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【递归】【迭代】【二叉树】
题目来源
解题思路
如果一棵树的左子树与右子树镜像对称，那么这两棵树是对称的。
因此，问题转换为：两棵树在什么情况下是互为镜像的，找出使两棵树互为镜像的条件，根据条件即可结局对称问题。
镜像条件如下：
- 两棵树的两个根节点具有相同的值；
- 每棵树的右子树都要与另一棵树的左子树镜像对称。
同时满足以上两个条件即可判断出两棵树是对称的。
二叉树问题通常都有两种递归和迭代的解法。
方法一：递归
递归出口是什么？
递归出口即可以直接判断的情况，包括：
- 两个节点都为空时，直接返回
true； - 一个节点为空，另一个不为空，返回
false。
如何往下递？
当前的两个节点表示的子树是否是对称的，取决于当前两节点的值以及左右子树是否对称。
只有当前两节点的值相等并且左右子树对称，这两个节点表示的子树才是对称的。
算法
实现一个判断两个节点 p 和 q 表示的子树是否是对称的函数 check：
- 如果
p = nullptr并且q = nullptr，直接返回true； - 如果
p ≠ nullptr或者q ≠ nullptr，直接返回false； - 最后
p和q表示的子树是否是对称与p->val == q->val && check(p->left, q->right) && check(p->right, q->left)一致，直接返回该表达式。
调用 check(root, root) 即得到最终答案。
复杂度分析
时间复杂度： O ( n ) O(n) O(n)， n n n 为二叉树中节点的数量。
空间复杂度： O ( n ) O(n) O(n)。
方法二：迭代
思路与算法
使用迭代解法需要用到队列。
首先我们引入一个队列，初始化时我们把根节点入队两次。每次提取两个节点并比较它们的值（队列中每两个连续的节点应该是相等的，而且它们的子树互为镜像），然后将两个节点的左右子节点按相反的顺序插入队列中。
当队列为空时，或者我们检测到树不对称，即从队列中取出两个不相等的连续节点时，该算法结束。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool check(TreeNode* u, TreeNode *v) {
queue<TreeNode*> q;
q.push(u); q.push(v);
while (!q.empty()) {
u = q.front(); q.pop();
v = q.front(); q.pop();
if (!u && !v)
continue;
if (!u || !v ||(u->val != v->val))
return false;
q.push(u->left);
q.push(v->right);
q.push(u->right);
q.push(v->left);
}
return true;
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
复杂度分析
时间复杂度： O ( n ) O(n) O(n)， n n n 为二叉树中节点的数量。
空间复杂度： O ( n ) O(n) O(n)，因为二叉树中的节点最多入队、出队一次，因此渐进的时间复杂度为 O ( n ) O(n) O(n)。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。
最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。
