本节判断一棵二叉树是否为对称二叉树,用深度优先算法和广度优先搜索算法均可以实现.
问题描述:
给定一棵二叉树,判断该二叉树是否为对称二叉树.
广度优先思路解析:
如果所有镜像对称位置上两节点都相同,就说明这棵树一定是对称的.那么如何对比对称位置上的两个节点比较方便呢?借助队列结构,令需要被比较的两个节点相邻,每次从队列中取出相邻的两个节点进行对比:如果相同,则继续;如果不同 ,则返回结果False.
确定了上述思路后,再考虑哪里是需要比较的两个节点.变量如下:
root变量:表示给定二叉树的根节点
queue变量:表示队列
root1:表示取出的第一个节点
root2:表示取出的第二个节点
root1和root2是对称位置上的两个节点
完整代码如下
def symmetric(root):# 如果根节点为空，返回True，因为空树被认为是对称的if not root: return True# 初始化一个队列，用于存放节点queue = []# 将根节点的左右子树加入队列queue.append(root.left)queue.append(root.right)# 循环，直到队列为空while queue:# 从队列中弹出两个节点root1 = queue.pop()root2 = queue.pop()# 如果两个节点都为空，继续循环if not root1 and not root2: continue# 如果一个为空，一个非空，或者两个节点的值不相等，则树不对称if not root1 or not root2: return Falseif root1.val != root2.val: return False# 如果当前节点的子节点不为空，则将子节点加入队列# 注意这里的顺序，左节点的左子叶和右节点的右子叶一组，左节点的右子叶和右节点的左子叶一组if root1.left or root2.left or root1.right or root2.right:queue.append(root1.left)queue.append(root2.right)queue.append(root1.right)queue.append(root2.left)# 如果所有节点都检查完毕，且没有发现不对称的情况，则树是对称的return True