AlgoPressAppearance
28-对称的二叉树
题目描述
https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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 题相同：https://leetcode.cn/problems/symmetric-tree/
思路1 : 做一个对称数，再用 IsMatch 去比较
实现代码
csharp
public class Solution {
private TreeNode CopyNode(TreeNode node){
if(node == null){
return null;
}
TreeNode newNode = new TreeNode(node.val);
newNode.left = CopyNode(node.right);
newNode.right = CopyNode(node.left);
return newNode;
}
private bool IsMatch(TreeNode A, TreeNode B){
// A 和 B 如果有一个为空，那么除非他们都为空，否则就是不相等
if(A == null || B == null){
return A == B;
}
return A.val == B.val && IsMatch(A.left, B.left) && IsMatch(A.right, B.right);
}
public bool IsSymmetric(TreeNode root) {
TreeNode newRoot = CopyNode(root);
return IsMatch(root,newRoot);
}
}
思路2 : 两个子树直接判断
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private bool IsSymmetricTree(TreeNode A, TreeNode B){
//如果 A 节点和 B 节点有一个为 null 那么除非他们都是 null 否则不相等
if(A == null || B == null){
return A == B;
}
//如果 A , B 都不为 null 判断当前值，并且分别判断左右子树
return A.val == B.val && IsSymmetricTree(A.left, B.right) && IsSymmetricTree(A.right, B.left);
}
public bool IsSymmetric(TreeNode root) {
if(root == null){
return true;
}
return IsSymmetricTree(root.left,root.right);
}
}
思路3 ：迭代方法【官方】
基本思路，将节点展开到Queue里面，展开的时候，按照 left,right right,left 的方式
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private bool IsSymmetricTree(TreeNode root){
if(root == null){
return true;
}
Queue<TreeNode> myQueue = new Queue<TreeNode>();
myQueue.Enqueue(root.left);
myQueue.Enqueue(root.right);
while(myQueue.Count > 0){
TreeNode A = myQueue.Dequeue();
TreeNode B = myQueue.Dequeue();
//都是空则继续
if(A == null && B == null){
continue;
}
//判断不等的情况就退出
if(A != null && B == null || A==null && B != null || A.val != B.val){
return false;
}
//对称加入左子节点和右子节点
myQueue.Enqueue(A.left);
myQueue.Enqueue(B.right);
myQueue.Enqueue(A.right);
myQueue.Enqueue(B.left);
}
//清空队列后发现没有不相等的情况，则为对称树
return true;
}
public bool IsSymmetric(TreeNode root) {
if(root == null){
return true;
}
return IsSymmetricTree(root);
}
}