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

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

方法思路

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

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

解决代码

import collections
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def 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是二叉树的节点数。

转载地址：http://ssgfk.baihongyu.com/