【算法第十二天7.26】二叉树层序遍历，翻转二叉树，对称二叉树

**二叉树层序遍历**

二叉树层序遍历是一种常见的遍历算法，它从最左边的节点开始，依次访问每一层的所有节点。这种遍历方式可以很好地体现出二叉树的结构。

### 层序遍历代码示例

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef levelOrderTraversal(root):
 if root is None:
 return queue = [root]
 while queue:
 node = queue.pop(0)
 print(node.value, end=" ")
 if node.left:
 queue.append(node.left)
 if node.right:
 queue.append(node.right)

# 构造一个示例二叉树root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("层序遍历结果:")
levelOrderTraversal(root) # 输出:12345

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef invertTree(root):
 if root is None:
 return # 交换左右子树 root.left, root.right = root.right, root.left # 递归翻转左、右子树 invertTree(root.left)
 invertTree(root.right)

# 构造一个示例二叉树root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("翻转前:")
levelOrderTraversal(root) # 输出:12345invertTree(root)

print("翻转后:")
levelOrderTraversal(root) # 输出:13254

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Nonedef isSymmetric(root):
 if root is None:
 return True # 使用递归检查左右子树是否对称 return isMirrorTree(root.left, root.right)

def isMirrorTree(tree1, tree2):
 if tree1 is None and tree2 is None:
 return True if tree1 is None or tree2 is None:
 return False # 检查当前节点的值是否相同 if tree1.value != tree2.value:
 return False # 递归检查左子树和右子树是否对称 return isMirrorTree(tree1.left, tree2.right) and isMirrorTree(tree1.right, tree2.left)

# 构造一个示例二叉树root = Node(1)
root.left = Node(2)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.right.left = Node(4)
root.right.right = Node(3)

print("是否对称:", isSymmetric(root)) # 输出: True