題目描述

請實現一個函數按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。

• 節(jié)點總數 <= 1000

題目樣例

示例

輸入

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

    3
   / \
  9  20
    /  \
   15   7

輸出

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

題目思考

1. 可以繼續(xù)利用昨天的方案嗎, 不行的話需要進行哪些改動?

解決方案

思路

• 回顧昨天那道題           劍指 Offer 32 - II. 從上到下打印二叉樹 II - leetcode 劍指offer系列, 我們是單獨打印每一層的節(jié)點, 只不過都是從左到右的方向
• 針對這道題, 我們可以額外維護一個變量, 記錄當前方向, 每次到下一層時就調換方向即可
• 也就是說, 只需要對昨天題目的代碼稍加改動就能搞定, 所以熟練掌握前面兩種 BFS 的模板是很有必要的, 很多問題都能在它們基礎上解決

復雜度

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

代碼

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        if not root:
            return res
        q = [root]
        # 初始從左到右遍歷
        fromleft = True
        while q:
            curlen = len(q)
            cur = []
            for node in q[:curlen]:
                cur.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if fromleft:
                res.append(cur)
            else:
                # 從右向左的話只需要將該層的值翻轉加入結果中即可
                res.append(cur[::-1])
            # 每一層結束后都調轉方向
            fromleft = not fromleft
            q = q[curlen:]
        return res