❓ 剑指 Offer 28. 对称的二叉树
难度：简单
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
限制：
0 <= 节点个数 <= 1000
注意：本题与 101. 对称二叉树 相同。
💡思路：
法一：递归
如果一个树的左子树与右子树镜像对称，那么这个树是对称的：
- 每次检查当前
root1和root2节点的值是否 相等; - 如果 相等 再判断左右子树是否对称:
root1的 左子树 对应root2的 右子树 ；root1的 右子树 对应root2的 左子树 ；- 同时成立时返回
true。
法二：迭代
方法一 中我们用 递归 的方法实现了对称性的判断，那么如何用迭代的方法实现呢？
- 要引入一个 队列
q，这是把递归程序改写成迭代程序的常用方法。
如果 root 不为空，将左右子树根节点分别加入队列：
- 只要队列不为空，每次从队列中提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像）；
- 然后将两个结点的左右子树按相反的顺序插入队列中；
- 插入
temp1的左子树后，紧接着插入temp2的右子树的根节点； - 然后再插入
temp1的右子树后，紧接着插入temp2的左子树的根节点；
- 插入
- 当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
🍁代码：(C++、Java)
法一：递归
C++
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:bool isSymTree(TreeNode* root1, TreeNode* root2){if(root1 == nullptr && root2 == nullptr) return true;if(root1 == nullptr || root2 == nullptr || (root1->val != root2->val)) return false;return isSymTree(root1->left, root2->right) && isSymTree(root1->right, root2->left);}
public:bool isSymmetric(TreeNode* root) {if(root == nullptr) return true;return isSymTree(root->left, root->right);}
};
Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {private boolean isSymTree(TreeNode root1, TreeNode root2){if(root1 == null && root2 == null) return true;if(root1 == null || root2 == null || (root1.val != root2.val)) return false;return isSymTree(root1.left, root2.right) && isSymTree(root1.right, root2.left);}public boolean isSymmetric(TreeNode root) {if(root == null) return true;return isSymTree(root.left, root.right);}
}
法二：迭代
C++
/*** Definition for a binary tree node.* 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 == nullptr) return true;queue<TreeNode*> q;q.push(root->left);q.push(root->right);while(!q.empty()){TreeNode* temp1 = q.front();q.pop();TreeNode* temp2 = q.front();q.pop();if(temp1 == nullptr && temp2 == nullptr) continue;if(temp1 == nullptr || temp2 == nullptr || (temp1->val != temp2->val)) return false;q.push(temp1->left);q.push(temp2->right);q.push(temp1->right);q.push(temp2->left);}return true;}
};
Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root == null) return true;Queue<TreeNode> q = new LinkedList<TreeNode>();q.offer(root.left);q.offer(root.right);while(!q.isEmpty()){TreeNode temp1 = q.poll();TreeNode temp2 = q.poll();if(temp1 == null && temp2 == null) continue;if(temp1 == null || temp2 == null || (temp1.val != temp2.val)) return false;q.offer(temp1.left);q.offer(temp2.right);q.offer(temp1.right);q.offer(temp2.left);}return true;}
}
🚀 运行结果：
🕔 复杂度分析：
- 时间复杂度： O ( n ) O(n) O(n)，其中
n为root的节点数，遍历了这棵树。 - 空间复杂度： O ( n ) O(n) O(n)，法一 的空间复杂度和递归使用的栈空间有关，这里递归层数不超过
n; 法二 需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过n个点。
题目来源：力扣。
放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我LeetCode主页 / CSDN—力扣专栏，每日更新！
