1 題目描述

給定一個二元樹，返回其節點值的之字形層序遍歷。換句話說，從左到右，逐層遍歷所有節點，然後每一層的節點值交替方向。
第 1 層從左到右，第 2 層從右到左，第 3 層從左到右，第 4 層從右到左，交替進行。

2 解法

2.1 我的解法

仔細看會發現一個規律，就是當我們在做層序遍歷的時候，我們可以透過BFS的方式，在不同的層，當發現是偶數層時，要從左到右，我們可以stack先塞right再left。而在奇數層時，要從右到左，我們可以stack先塞left再right。

# 透過pop的方式取出最晚進去的節點
node = nodes.pop()
# 紀錄當前的層
cur_level.append(node.val)
# 如果是偶數層 Left到Right，因此我們先塞Right再Left，按照後進先出的方式達到 Left -> Right 
if level % 2 == 1:
    if node.right: next_level.append(node.right)
    if node.left: next_level.append(node.left)
# 如果是奇數層 Right到Left，因此我們先塞Left再Right，按照後進先出的方式達到 Right -> Left
else: 
    if node.left: next_level.append(node.left)
    if node.right: next_level.append(node.right)

基本上我們就完成了

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

        def helper(nodes, lvl):
            cur_lvl = []
            next_lvl = []
            # 如果沒有節點了，就停止
            if len(nodes) == 0:
                return
            # 如果 nodes 存在
            while nodes:
                node = nodes.pop()
                cur_lvl.append(node.val)
                # 如果是偶數層 Left到Right，因此我們先塞Right再Left，按照後進先出的方式達到 Left -> Right
                if lvl % 2 == 0:
                    if node.left: next_lvl.append(node.left)
                    if node.right: next_lvl.append(node.right)
                # 如果是奇數層 Right到Left，因此我們先塞Left再Right，按照後進先出的方式達到 Right -> Left
                else:
                    if node.right: next_lvl.append(node.right)
                    if node.left: next_lvl.append(node.left)
            # 將當前層的節點值存放在答案中
            ans.append(cur_lvl)
            # 遞迴下一層
            helper(next_lvl, lvl+1)

        ans = []
        if root:
            helper([root], 0)
        return ans

2.2 使用迭代的方式

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        result = []
        stack = [root]
        level = 0
        while stack:
            next_level, values = [], []
            for node in stack:
                values.append(node.val)
                # 每一層從左到右
                if node.left: next_level.append(node.left)
                if node.right: next_level.append(node.right)
            # 如果是奇數層，就反轉
            if level % 2 == 1:
                values = values[::-1]
            # 然後直接塞入答案
            result.append(values)
            stack = next_level
            level += 1
        return result