(树) 剑指 Offer 28. 对称的二叉树 —

❓ 剑指 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)$ ，其中 n 为root 的节点数，遍历了这棵树。
空间复杂度： $O (n)$ ，法一的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n ; 法二需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过 n 个点。