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

• 概要
• 問題
• 解法

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

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

次回
ゼロから始めるLeetCode Day106「209. Minimum Size Subarray Sum」

Twitterやってます。

問題

111. Minimum Depth of Binary Tree
難易度はEasy。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、二分木が与えられた場合、その最小深度を求めよ、というものです。
なお、最小深度とは、ルートノードから最も近い葉までの最短経路に沿ったノードの数である。
注意：葉とは，子を持たないノードのことである。

解法

# 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 minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = [(root,1)]
        for node, depth in queue:
            if node.left:
                queue.append((node.left,depth+1))
            if node.right:
                queue.append((node.right,depth+1))
            elif not node.left:
                return depth
# Runtime: 44 ms, faster than  81.39%  of  Python3  online submissions for  Minimum Depth of Binary Tree.
# Memory Usage: 14.8 MB, less than  96.23%  of  Python3  online submissions for  Minimum Depth of Binary Tree.

今までなら深さ優先探索で解いていましたが、今回は幅優先探索に慣れるために幅優先探索で解いてみました。

queueで木と深さを管理し、仮に要素が存在するなら存在する要素を追加、そして値をプラス1することで要素と深さを移行していきます。

今回はあくまで最短経路の探索なので、要素が無くなった時点で深さを返して終了です。

木構造が出てくるととりあえず深さ優先探索か幅優先探索で解くことを考えますが、使い分けがイマイチうまくできていないのでもっと勉強して慣れていきたいですね。

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