ゼロから始めるLeetCode Day83 「102. Binary Tree Level Order Traversal」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day82「392. Is Subsequence」

次回
まだ

Twitterやってます。

問題

102. Binary Tree Level Order Traversal
難易度はMedium。
前回と同じく問題集からの抜粋です。

問題としては、バイナリツリーが与えられた場合、そのノードの値の階層順の横の同値をまとめたリストを返すアルゴリズムを設計してください。(すなわち、左から右へ、レベルごとに)というものです。

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

例はこんな感じ。
言いたいことは理解してもらえたと思います。

解法

DFSで解きました。

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans,level = [],0
        self.dfs(root,level,ans)
        return ans
    
    def dfs(self,root,level,ans):
        if not root:
            return
        if len(ans) < level+1:
            ans.append([])
        ans[level].append(root.val)
        self.dfs(root.left,level+1,ans)
        self.dfs(root.right,level+1,ans)
# Runtime: 32 ms, faster than 86.02% of Python3 online submissions for Binary Tree Level Order Traversal.
# Memory Usage: 14.2 MB, less than 43.09% of Python3 online submissions for Binary Tree Level Order Traversal.

シンプルなDFSですね。
リストとして返すということが決まっているので、リストの長さをとって上げると階層の要素を上手く網羅できます。

今回は慣れている深さ優先探索で解いてしまいましたが、discussにはBFSで解いた例や、キューを使って解いた解答もあったりと、個人の好きな解き方が現れそうな感じの問題ですね。

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