題目出處

103. Binary Tree Zigzag Level Order Traversal

難度

medium

個人範例程式碼

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        ans = []
        this_layer = [root]
        reverse_flag = False

        while this_layer:
            this_layer_ans = []
            next_layer = []
            for node in this_layer:
                this_layer_ans.append(node.val)

                if node.left:
                    next_layer.append(node.left)
                if node.right:
                    next_layer.append(node.right)

            if reverse_flag:
                this_layer_ans.reverse()

            ans.append(this_layer_ans[:]) # deepcopy
            this_layer = next_layer
            reverse_flag = not reverse_flag

        return ans

算法說明

類似 level order traversal 的邏輯，只不過在 zigzag 中我們要做的是間隔 layer 反轉輸出的結果。

至於要反轉的話，加一個反轉 flag 即可輕鬆完成

input handling

如果沒有 root，return []

Boundary conditions

透過 layer 一層一層循環，直到下一層 layer 無東西為止。

Reference

• Python List reverse()