101. 对称二叉树
题目:
给你一个二叉树的根节点 root
, 检查它是否轴对称。
示例:
示例 1:
输入:root = [1,2,2,3,4,4,3]
输出:true
示例 2:
输入:root = [1,2,2,null,3,null,3]
输出:false
提示:
- 树中节点数目在范围
[1, 1000]
内 -100 <= Node.val <= 100
**进阶:**你可以运用递归和迭代两种方法解决这个问题吗?
解题:
方法一:递归
二叉树对称,说明它们关于根节点镜像,左子树=右子树,反之亦然。因此可以用两个指针,同时向根节点的左右子树两个方向遍历。
p指针左移,则q指针右移,每次移动检查当前指针所指向的节点的值是否相等,反之亦然。
/**
* 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 *p, TreeNode *q) {
// 如果两个节点都为空,也是对称的
if(!p && !q) return true;
// 如果其中一个节点不为空,不对称
if(!p || !q) return false;
// 节点值不相等,不对称
// 递归检查左子树的左子树与右子树的右子树,以及左子树的右子树与右子树的左子树
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
通俗易懂版本
class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
// 如果两个节点都为空,也是对称的
if(p == nullptr && q == nullptr) {
return true;
}
// 如果其中一个节点不为空,不对称
if(p == nullptr || q == nullptr) {
return false;
}
// 节点值不相等,不对称
if(p->val != q->val) {
return false;
}
// 递归检查左子树的左子树与右子树的右子树,以及左子树的右子树与右子树的左子树
return check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};
复杂度分析
假设树上一共 n 个节点。
- 时间复杂度:这里遍历了这棵树,渐进时间复杂度为 O(n)。
- 空间复杂度:这里的空间复杂度和递归使用的栈空间有关,这里递归层数不超过 n,故渐进空间复杂度为 O(n)。
方法二:迭代
基本思路是使用队列,将每一层的节点按照对称的顺序加入队列,然后依次比较队列中的节点是否对称。每次从队列中取出两个节点进行比较,并按照对称的顺序将它们的子节点加入队列。**要注意的是根节点要加入队列两次。**当队列为空时,或者我们检测到树不对称(即从队列中取出两个不相等的连续结点)时,该算法结束。
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),同「方法一」。
-
空间复杂度:这里需要用一个队列来维护节点,每个节点最多进队一次,出队一次,队列中最多不会超过 n 个点,故渐进空间复杂度为 O(n)。