TreeNode 类与层序 BFS
从数组构建二叉树，使用 deque 实现 BFS 逐层打印，并用 BFS 求最大深度。
TreeNode 类与层序 BFS 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
TreeNode 类基础
二叉树是一种层次化数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。在 Python 中，我们使用一个简单的类来表示节点：class TreeNode: def __init__(self, val=0, left=None, right=None)。面试中的每个树问题都从这个定义开始——几乎在每个 LeetCode 树问题的样板代码中，您都会看到它。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)从数组构建树
面试题通常会给出用层序数组表示的树，其中 None 表示缺失的节点。给定索引 i 后，左子节点位于 2i+1，右子节点位于 2i+2。编写一个辅助函数，将这个数组反序列化为相互连接的 TreeNodes，是一项很有价值的实用技能，可以在练习时节省时间。
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)什么是 BFS，为什么使用队列
广度优先搜索（BFS）会先访问深度为 d 的所有节点，然后再访问深度为 d+1 的任何节点。这种逐层遍历正是队列（FIFO）所提供的功能：将根节点入队，然后逐个处理节点，并在处理过程中将每个节点的子节点入队。Python 的 collections.deque 为 appendleft 和 popleft 提供 O(1) 操作，因此相比普通列表，它是更合适的选择。
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4按层 BFS：按层分组
标准 BFS 变体会在每次迭代开始时记录队列大小，以此将节点分组到不同层中。准确处理这么多个节点，收集它们的值，然后进入下一层。这样会产生一个列表的列表——这是面试中非常常见的输出格式，适用于二叉树层序遍历、之字形遍历和右侧视图等问题。
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]通过 BFS 求最大深度
二叉树的最大深度等于其 BFS 遍历中的层数。只需统计完成层循环的次数即可。这会得到一个 time 复杂度为 O(n)、空间复杂度为 O(w) 的解法，其中 w 是树的最大宽度。对于平衡树，w 为 O(n/2)，因此最坏情况下的空间复杂度为 O(n)。
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3二叉树的右侧视图
右侧视图返回从右侧观察树时最后可见的节点——也就是 BFS 遍历中每一层的最后一个元素。这是层序 BFS 的直接应用：在每个层循环中收集最后一个节点。time 复杂度为 O(n)，队列的空间复杂度为 O(w)。
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]锯齿形层序遍历
在锯齿形遍历中，奇数层从左到右收集，偶数层从右到左收集。最简洁的实现方式是保持 BFS 队列不变，只在将各层列表追加到结果之前，简单地反转交替的层列表。使用一个布尔标志跟踪方向，并在每层结束时翻转它。这样可以避免在内层循环中处理双端队列的复杂性。
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))BFS 空间复杂度分析
BFS 使用 O(w) 的空间，其中 w 是树的最大宽度。对于包含 n 个节点的完美二叉树，最后一层有 (n+1)/2 个节点，因此 BFS 可以在队列中同时保存最多 n/2 个节点。对于宽而平衡的树，这使得 BFS 的空间消耗比 DFS (O(h))更差；但对于深度很大且退化的树，BFS 的空间消耗更好，因为此时 DFS 的调用栈深度等于 n。
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')二叉树的层平均值
计算每一层的平均值是 BFS 的另一个直接应用。将某一层的所有值相加，除以节点数量，然后追加到结果列表中。这个问题考查您是否能在层循环中进行算术运算。在 Python 3 中请始终使用 float 除法（即 / 运算符），并在开始时处理空树这一边界情况。
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]使用 BFS 求最小深度
最小深度是从根节点到最近叶节点（没有子节点的节点）的距离。BFS 可以最优地找到它：在层序遍历中首先遇到的叶节点一定处于最小深度。遇到叶节点后立即返回当前深度。最坏情况下时间复杂度为 O(n)，但对于平衡树，通常会更早结束。
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2连接同层节点
填充右侧指针问题要求将每个节点连接到同层右侧的节点。使用 BFS 可以直接完成：在每层循环中，除最后一个节点外，为所有节点设置 node.next = q[0]。这是一个经典例子：BFS 让解决方案一目了然，而 DFS 则需要仔细跟踪跨越不同子树的指针。
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')快速检查
测试您对本课中数据结构 & 算法——编程面试准备相关概念的理解。
课程回顾
本课介绍了：TreeNode 类的定义以及如何根据数组构建树，使用双端队列进行层序 BFS并利用层大小技巧将节点分组，以及包括最大深度、最小深度、右视图、锯齿形遍历和各层平均值在内的应用。接下来我们将探索递归 DFS 遍历顺序。
常见问题解答
「TreeNode 类与层序 BFS」课时是免费的吗？
是的 — 「TreeNode 类与层序 BFS」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「TreeNode 类与层序 BFS」这节课中我会学到什么？
从数组构建二叉树，使用 deque 实现 BFS 逐层打印，并用 BFS 求最大深度。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「TreeNode 类与层序 BFS」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- TreeNode 类与层序 BFS
- 中序、前序、后序 DFS
- 直径、高度与平衡树
- 路径和与最近公共祖先