59 按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

解题思路

核心思想：使用双端队列（deque）进行层序遍历。

关键步骤：

1. 使用flag标记当前层是否需要反转
2. 每层遍历时，根据flag决定从左还是从右取节点

时间复杂度：O(n) 空间复杂度：O(n)

Python 实现

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def print_z_shape(root):
    """
    按之字形打印二叉树

    Args:
        root: 二叉树根节点

    Returns:
        list: 每层的节点值
    """
    if not root:
        return []

    result = []
    dq = deque([root])
    left_to_right = True

    while dq:
        level_size = len(dq)
        level = []

        for _ in range(level_size):
            if (left_to_right):
                node = dq.popleft()
                level.append(node.val)
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)
            else:
                node = dq.pop()
                level.append(node.val)
                if node.right:
                    dq.appendleft(node.right)
                if node.left:
                    dq.appendleft(node.left)

        result.append(level)
        left_to_right = not left_to_right

    return result


# 测试代码
if __name__ == "__main__":
    # 构建树:
    #     1
    #    / \
    #   2   3
    #  / \ / \
    # 4  5 6  7
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(7)

    result = print_z_shape(root)
    for i, level in enumerate(result):
        print(f"第{i+1}层: {level}")

# 输出:
# 第1层: [1]
# 第2层: [3, 2]
# 第3层: [4, 5, 6, 7]