題目描述

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

• 節點總數 <= 1000

題目樣例

示例

輸入

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

    3
   / \
  9  20
    /  \
   15   7

輸出

[
  [3],
  [9,20],
  [15,7]
]

題目思考

1. 如何記錄當前層的信息?

解決方案

思路

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

復雜度

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

代碼

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