秋招算法备战第15天 | 层序遍历、226.翻转二叉树、101.对称二叉树

**秋招算法备战第15 天**

今天我们将讨论三道经典的算法题目：层序遍历、二叉树翻转和对称二叉树。这些题目都是面试常见的问题，掌握它们可以帮助你提高算法能力。

### 一、层序遍历**问题描述**

给定一个二叉树，输出其每一层的节点值。

**示例**

输入：[3,9,20,null,null,15,7]

输出：

[
[3],
[9,20],
[15,7]
]

**解决方案**

我们可以使用队列来实现层序遍历。首先，我们将根节点入队，然后开始循环直到队列为空。

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

**注释**

* 我们首先检查根节点是否为空。如果是，则直接返回一个空列表。
* 然后，我们创建一个队列并将根节点入队。
* 开始循环直到队列为空。每次循环中，我们都会处理当前层的所有节点，并将下一层的节点入队。
* 最终，我们会得到每一层的节点值，按照层序遍历的顺序。

### 二、226.翻转二叉树**问题描述**

给定一个二叉树，输出其翻转后的结果。

**示例**

输入：[4,2,7,1,3,6,9]

输出：

[
[9],
[6,3],
[7,2,4]
]

**解决方案**

我们可以使用递归来实现二叉树的翻转。首先，我们定义一个函数来交换两个节点的值，然后再递归地交换每个子树的根节点。

class Solution:
 def invertTree(self, root):
 if not root:
 return None self.invert(root)
 return root def invert(self, node):
 if not node:
 return # 交换当前节点的值 node.val = node.val ^1 # 递归地交换子树的根节点 self.invert(node.left)
 self.invert(node.right)

**注释**

* 我们首先检查根节点是否为空。如果是，则直接返回 None。
* 然后，我们定义一个函数来交换两个节点的值，并递归地交换每个子树的根节点。

### 三、101.对称二叉树**问题描述**

给定一个二叉树，输出其是否为对称二叉树。

**示例**

输入：[1,2,2,3,4,4,3]

输出：

True**解决方案**

我们可以使用递归来实现对称二叉树的检测。首先，我们定义一个函数来比较两个子树是否相等，然后再递归地比较每个子树。

class Solution:
 def isSymmetric(self, root):
 if not root:
 return True return self.isMirror(root.left, root.right)
 def isMirror(self, left, right):
 if not left and not right:
 return True if not left or not right:
 return False return (left.val == right.val) and self.isMirror(left.right, right.left) and self.isMirror(left.left, right.right)

**注释**

* 我们首先检查根节点是否为空。如果是，则直接返回 True。
* 然后，我们定义一个函数来比较两个子树是否相等，并递归地比较每个子树。

通过掌握这些经典的算法题目，你可以提高你的算法能力并更好地准备面试。