101。对称二叉树题目给定一棵二叉树，检查它是否镜像对称。例如，二叉树[1,2,2,3,4,4,3]是对称的。1/\22/\/\3443但下面的[1,2,2,null,3,null,3]不是镜像对称的：1/\22\\33高级：你可以递归和迭代可以用来解决这个问题吗？如何解决判断二叉树是否镜像对称的问题？如下：如果根节点为null，直接返回True；当根节点不为null时，判断左右子树是否对称：判断root.left和root.right的节点值是否相同；判断root.left的左子树是否与root相同。right的右子树是对称的。判断root.left的右子树是否与root.right的左子树对称。根据题目的【进阶】部分，本文将从递归和迭代两种思路来解决这个问题。思路：递归根据上面判断二叉树是否对称的思路，首先设置递归终止条件：如果都是空指针，则返回True，其中一个不为空，则返回False递归具体过程：先判断当前两个指针节点的值是否相等，判断t1的左子树和t2的右子树是否对称。判断t1的右子树和t1的左子树是否对称。具体代码实现见【代码实现：递归】。思路：迭代还是按照一开始的思路判断二叉树的对称性，这次是用迭代的方式实现的。这里需要引入一个队列。具体方法：初始化时，对根节点进行两次入队。循环时，每次两次从队列中取出两个节点，比较它们的值（因为子树互为镜像，所以它们的值应该相等）。再次入队时，将两个节点的左右子节点颠倒顺序入队。（例如：t1节点的左子节点和t2节点的右子节点连续出队）循环结束的条件是队列为空，或者连续出队的两个节点都是不相等。具体实现代码见【代码实现：迭代】代码实现代码实现：递归#二叉树节点的定义#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defisSymmetric(self,root:TreeNode)->bool:returnself.check(root,root)defcheck(self,t1,t2):ift1==Noneandt2==None：如果t1==None或t2==None，则返回True：返回False左）代码实现：迭代#定义二叉树节点。#classTreeNode：#def__init__（self，x）：#self.val=x#self.left=None#self.right=Noneclass解决方案：defisSymmetric（self,root:TreeNode)->bool:#构建，初始化队列#将根节点入队两次queue=[]queue.append(root)queue.append(root)#循环开始whilelen(queue)!=0:#先连续出队，抽取两个节点进行比较t1=queue.pop()t2=queue.pop()ift1==Noneandt2==None:continue#当两个节点不相等时，returnFalseift1==Noneort2==Noneort1.val!=t2.val:returnFalse#重新入队，将两个节点的左右子节点倒序入队queue.append(t1.left)队列。append(t2.right)queue.append(t1.right)queue.append(t2.left)returnTrue实现结果实现结果：递归实现结果：迭代总结按照递归的思路解决问题，按照迭代迭代题意判断是否镜像对称的思路：这里是判断根不为空（根节点为空，直接返回True）；判断root.left和root.right节点值是否相同；判断root.left的左子树和root.right的右子树是否对称；判断root.left的右子树和root.right的左子树是否对称。递归实现具体过程：终止条件：当所有指针都为空时，返回True；当其中一个指针为空时，返回False；判断两个指针的节点值是否相同；判断t1的左子树是否与t2的右子树对称判断t1的右子树是否与t2的左子树对称。引入一个队列，首先初始化队列，先对root进行两次入队；在循环开始的时候，先连续出队两次，取出两个节点，比较它们的值（两个相邻的值应该是相等的，因为左右子树是各自的镜像other)将两个节点的左右子节点倒序入队（例如t1的左节点和t2的右节点依次入队）循环结束的条件，当队列为空时，或出队的两个节点不相等（即不对称）。欢迎关注微信公众号《书所集录》
