題目描述

從上到下按層打印二叉樹，同一層的節(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. 如何記錄當(dāng)前層的信息?

解決方案

思路

• 相比昨天那道題, 這里需要把每層節(jié)點(diǎn)都單獨(dú)打印出來, 如果仍使用昨天的方法, 就無法知道每層的邊界在哪, 所以需要做出一些改變
• 如果我們能夠記錄下當(dāng)前層的節(jié)點(diǎn)邊界, 然后當(dāng)前層的子節(jié)點(diǎn)都加入隊(duì)列后, 將隊(duì)列更新為從下一層節(jié)點(diǎn)起點(diǎn)開始, 這樣就確保每一層都單獨(dú)被記下來了
• 這就是今天這道題的思路: 按照每層來循環(huán), 存當(dāng)前層的節(jié)點(diǎn)長(zhǎng)度 curlen, 新追加的下層節(jié)點(diǎn)起點(diǎn)下標(biāo)自然就是 curlen, 所以當(dāng)前層遍歷完之后只需要將隊(duì)列切片成 curlen 及以后的部分即可
• 同樣的, 由于是樹, 每個(gè)節(jié)點(diǎn)只需要遍歷一次, 所以不需要 visit 集合
• 下面的代碼又是個(gè)人覺得比較通用的另一個(gè) BFS 模板, 它適用于需要單獨(dú)處理每一層節(jié)點(diǎn)的情況, 供大家參考

復(fù)雜度

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

代碼

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res
        q = [root]
        while q:
            # 當(dāng)前層長(zhǎng)度
            curlen = len(q)
            curlevel = []
            for node in q[:curlen]:
                # 將當(dāng)前層的節(jié)點(diǎn)值依次加入結(jié)果中
                curlevel.append(node.val)
                # 只追加非空子節(jié)點(diǎn)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(curlevel)
            # 隊(duì)列切片, 開始處理下一層
            q = q[curlen:]
        return res