題目描述

從上到下打印出二叉樹的每個節點，同一層的節點按照從左到右的順序打印。

• 節點總數 <= 1000

題目樣例

示例

輸入

給定二叉樹: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

輸出

[3,9,20,15,7]

題目思考

1. 哪些數據結構可以做到按層輸出?

解決方案

思路

• 經典的 BFS 思路, 將當前節點的左右非空子節點追加到隊列結尾, 然后繼續往后遍歷隊列, 最終整個隊列就是最后的結果
• 由于這里是樹, 所以每個節點只可能被加入隊列訪問一次, 無需額外的 visit 集合
• 另外這道題不需要分開保存每一層的節點, 所以這里不需要記錄當前層的長度之類的情況, 可以直接一次循環搞定
• 數據結構方面, 可以采用列表 + 動態的 for 循環(python 3 適用, 其他語言可能不支持遍歷過程中更改容器)或者雙端隊列 + while 循環(所有語言通用, 每次 pop 最左邊的元素作為當前節點)
• 下面的代碼是個人覺得比較通用的 BFS 模板, 包括列表和雙端隊列兩種方式的實現, 適用于不需要單獨處理每一層節點的情況, 供大家參考

復雜度

• 時間復雜度           O(N)
• 每個節點只需要遍歷一次
• 空間復雜度           O(N)
• 額外需要一個列表/雙端隊列

代碼

方案 1 - 列表 + for 循環

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        # 方案1: 列表+for循環
        if not root:
            return []
        q = [root]
        for node in q:
            # 只將非空子節點追加到隊列
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return [x.val for x in q]

方案 2 - 雙端隊列 + while 循環

import collections

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        # 方案2: 雙端隊列+while循環
        if not root:
            return []
        q = collections.deque([root])
        res = []
        while q:
            node = q.popleft()
            res.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return res