22 从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

示例：

树:
    1
   / \
  2   3
 / \
4   5

输出: [1, 2, 3, 4, 5]

解题思路

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

关键步骤：

1. 将根节点入队
2. 队列不为空时循环：
   • 出队一个节点，记录其值
   • 如果有左子节点，入队
   • 如果有右子节点，入队

时间复杂度：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_from_top_to_bottom(root):
    """
    从上往下打印二叉树（层序遍历）

    Args:
        root: 二叉树根节点

    Returns:
        list: 层序遍历结果
    """
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()
        result.append(node.val)

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

    return result


# 测试代码
if __name__ == "__main__":
    # 创建树:
    #     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("层序遍历:", print_from_top_to_bottom(root))  # [1, 2, 3, 4, 5]

图解

层序遍历过程:

初始队列: [1]

出队1, 记录1, 入队2,3 → 队列: [2,3]
出队2, 记录2, 入队4,5 → 队列: [3,4,5]
出队3, 记录3           → 队列: [4,5]
出队4, 记录4           → 队列: [5]
出队5, 记录5           → 队列: []

结果: [1, 2, 3, 4, 5]