題目描述

從上到下打印出二叉樹的每個(gè)節(jié)點(diǎn)，同一層的節(jié)點(diǎn)按照從左到右的順序打印。

• 節(jié)點(diǎn)總數(shù) <= 1000

題目樣例

示例

輸入

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

    3
   / \
  9  20
    /  \
   15   7

輸出

[3,9,20,15,7]

題目思考

1. 哪些數(shù)據(jù)結(jié)構(gòu)可以做到按層輸出?

解決方案

思路

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

復(fù)雜度

• 時(shí)間復(fù)雜度           O(N)
• 每個(gè)節(jié)點(diǎn)只需要遍歷一次
• 空間復(fù)雜度           O(N)
• 額外需要一個(gè)列表/雙端隊(duì)列

代碼

方案 1 - 列表 + for 循環(huán)

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

方案 2 - 雙端隊(duì)列 + while 循環(huán)

import collections

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        # 方案2: 雙端隊(duì)列+while循環(huán)
        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