代码随想录第十五天|层序遍历、翻转二叉树、对称二叉树

**代码随想录第十五天**

今天我们将讨论三道经典的算法题目：层序遍历、二叉树翻转和对称二叉树。

### 一、层序遍历层序遍历（Breadth-First Search，BFS）是指从根结点开始，依次访问每一层的所有结点。这种遍历方式适用于需要按层次访问结点的场景。

####代码示例

from collections import dequeclass TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef levelOrder(root):
 if not root:
 return []

 result = []
 queue = deque([root])

 while queue:
 level = []
 for _ in range(len(queue)):
 node = queue.popleft()
 level.append(node.val)
 if node.left:
 queue.append(node.left)
 if node.right:
 queue.append(node.right)

 result.append(level)

 return result

####代码注释* 我们首先检查根结点是否为空。如果是，则直接返回一个空列表。
* 初始化结果列表和队列，分别用于存储每一层的值和结点。
* 进入循环直到队列为空。
* 每次循环中，我们首先创建一个新列表来存储当前层的值，然后遍历队列，取出结点并将其值添加到列表中。如果结点有左或右孩子，则将它们添加到队列中。
* 最后，将当前层的值添加到结果列表中。

### 二、翻转二叉树翻转二叉树是指交换每个结点的左右子树。这种操作可以用于创建新的二叉树或修改原有的二叉树结构。

####代码示例

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef invertTree(root):
 if not root:
 return None # 交换左右子树 root.left, root.right = root.right, root.left # 递归交换左、右子树的左右子树 invertTree(root.left)
 invertTree(root.right)

 return root

####代码注释* 我们首先检查根结点是否为空。如果是，则直接返回 None。
* 交换根结点的左右子树。
* 递归交换左、右子树的左右子树。

### 三、对称二叉树对称二叉树是指每个结点的左右子树都是镜像对称的。这种结构可以用于创建新的二叉树或修改原有的二叉树结构。

####代码示例

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef isSymmetric(root):
 if not root:
 return True # 递归检查左右子树是否对称 return isMirror(root.left, root.right)

def isMirror(left, right):
 if not left and not right:
 return True if not left or not right:
 return False # 检查左、右子树的值和结构是否相等 return (left.val == right.val) and 
 isMirror(left.left, right.right) and 
 isMirror(left.right, right.left)

####代码注释* 我们首先检查根结点是否为空。如果是，则直接返回 True。
* 递归检查左右子树是否对称。
* 检查左、右子树的值和结构是否相等。

以上就是今天我们讨论的三道经典算法题目：层序遍历、二叉树翻转和对称二叉树。这些题目可以帮助你提高对数据结构和算法的理解，特别是在处理二叉树时。