从上到下打印二叉树1

Leetcode Link: 剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode） (leetcode-cn.com)

题目

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

解法一

思路：见非递归的层次遍历

题解：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root: 
            return []
        res = []
        queue = collections.deque()
        queue.append(root)
 
        while queue:
            cur = queue.popleft()
            res.append(cur.val)
            if cur.left: queue.append(cur.left)
            if cur.right: queue.append(cur.right)
        return res

Python 中的队列

1. 使用 import queue 的包，时间复杂度好像有点高
2. 使用列表 list的.pop(0) 时间复杂度为 $O(N)$
3. 使用使用 collections 中的双端队列 deque() ，其 popleft() 方法可达到 $O(1)$ 时间复杂度

启发和联系