本文共 1382 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要实现二叉树的之字型层次遍历。这种遍历方式是在每一层中，节点的访问顺序会交替变化，即从左到右，然后右到左，再从左到右，依此类推。

方法思路

我们可以使用广度优先搜索（BFS）来遍历二叉树，并在每一层中根据指定的方向收集节点值。具体步骤如下：

这种方法确保我们能够按层次和指定的方向收集节点值，得到正确的结果。

解决代码

import collectionsclass TreeNode:    def __init__(self, val):        self.val = val        self.left = None        self.right = Nonedef zigzagLevelOrder(root):    result = []    if not root:        return result    queue = collections.deque([root])    direction = True  # True表示左到右，False表示右到左    while queue:        currentLevelSize = len(queue)        currentLevel = []        for _ in range(currentLevelSize):            node = queue.popleft()            currentLevel.append(node.val)            if node.left:                queue.append(node.left)            if node.right:                queue.append(node.right)        if not direction:            currentLevel = currentLevel[::-1]        result.append(currentLevel)        direction = not direction    return result

代码解释

• TreeNode类：定义了二叉树的节点结构，每个节点包含值、左子节点和右子节点。
• zigzagLevelOrder函数：实现了之字型层次遍历。
  • 初始化队列，并将根节点加入队列。
  • 使用方向变量控制遍历方向。
  • 在每次循环中，处理当前层的所有节点，收集它们的值，并根据方向反转顺序。
  • 将处理后的节点值添加到结果列表中。
  • 处理左子和右子节点，更新队列。
  • 交换方向，继续处理下一层节点。

这种方法确保了我们能够高效地完成二叉树的之字型层次遍历，时间复杂度为O(n)，空间复杂度为O(n)，其中n是二叉树的节点数。