ゼロから始めるLeetCode Day104「103. Binary Tree Zigzag Level Order Traversal」

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day103「122. Best Time to Buy and Sell Stock II」

次回
ゼロから始めるLeetCode Day105「111. Minimum Depth of Binary Tree」

Twitterやってます。

問題

103. Binary Tree Zigzag Level Order Traversal
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、二分木が与えられた場合、そのノードの値のジグザグレベル順のトラバーサルを返すという問題です。

（左から右へ、次のレベルでは右から左へ、その間では交互に）。(つまり、左から右へ、そして次のレベルは右から左へ、そしてその間を交互に)

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

解法

# 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: TreeNode) -> List[List[int]]:
        if not root:
            return []
        queue,ans,direction = deque([root]),[], 1 
        while queue:
            depth = []
            for i in range(len(queue)):
                node = queue.popleft()
                depth.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(depth[::direction])
            direction *= (-1)
        return ans
# Runtime: 24 ms, faster than 98.89% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.
# Memory Usage: 14 MB, less than 64.19% of Python3 online submissions for Binary Tree Zigzag Level Order Traversal.

それぞれの階層のノード値を配列にまとめて返す、というものなので、典型的なBFSの問題ですね。

BFSではキューを使って構造を管理するので、Pythonでは基本的に組み込み関数のdequeを使ってそれぞれの階層を管理します。
directionという変数はどちら側から配列の要素をansに追加する配列に代入するかをスライスで管理するためのもので、それぞれの最初は順に、次は逆順に・・・といった風に代入されるようにwhile文を回す度にスイッチされるようになっています。
それ以外に関してはBFSの基本的な実装です。

では今回はここまで。
お疲れ様でした。