【LeetCode】 111. Minimum Depth of Binary Tree 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1：幅優先探索
2. 解答2：深さ優先探索
補足・参考・感想

問題

原文

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]

Output: 5

Constraints:

The number of nodes in the tree is in the range [0, 10⁵].

-1000 <= Node.val <= 1000

内容

二分木が与えられます。最小の深さを見つけてください。最小の深さは根ノードから一番近い葉ノードまで下った時の深さを指します。

※正しくない可能性があります。

方針

・根ノードから葉ノードまでの最短距離を調べる問題

・葉ノードは子を持たないノード。左右どちらにも子ノードがないノードの深さを調べる

・幅優先探索と深さ優先探索でそれぞれ解答

解答

解答1：幅優先探索

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        #木がない場合
        if not root:
            #0を返す
            return 0
        #キューを用意
        q = deque()
        #キューに木を格納
        q.append(root)
        print(q)
        #高さを0に設定
        depth = 0
        #BFS：キューに要素がある限り(全てのノードに対して)繰り返す
        while q:
            #キューの要素数(残りのノードの数)を変数に格納
            level_size = len(q)
            #深さをインクリメント
            depth += 1
            #キューの要素数分だけ(ノードの数だけ)繰り返す
            for i in range(level_size):
                #キューから要素を取り出す
                current = q.popleft()
                #左右両方の子ノードがない場合
                if not current.left and not current.right:
                    #深さを返す[1]
                    return depth
                #左の子ノードがある場合
                if current.left:
                    #キューに左の子ノードを追加
                    q.append(current.left)
                #右の子ノードがある場合
                if current.right:
                    #キューに右の子ノードを追加
                    q.append(current.right)
        #深さを返す
        return depth

class Solution:

def minDepth(self, root: Optional[TreeNode]) -> int:

#木がない場合

if not root:

#0を返す

return 0

#キューを用意

q = deque()

#キューに木を格納

q.append(root)

print(q)

#高さを0に設定

depth = 0

#BFS：キューに要素がある限り(全てのノードに対して)繰り返す

while q:

#キューの要素数(残りのノードの数)を変数に格納

level_size = len(q)

#深さをインクリメント

depth += 1

#キューの要素数分だけ(ノードの数だけ)繰り返す

for i in range(level_size):

#キューから要素を取り出す

current = q.popleft()

#左右両方の子ノードがない場合

if not current.left and not current.right:

#深さを返す[1]

return depth

#左の子ノードがある場合

if current.left:

#キューに左の子ノードを追加

q.append(current.left)

#右の子ノードがある場合

if current.right:

#キューに右の子ノードを追加

q.append(current.right)

#深さを返す

return depth

[1]

・幅優先探索はある階層の各ノードを全て調べてから次のノードに移るイメージがあるが、この書き方だと左側の子ノードが葉で、右側の子ノードがさらに子ノードを持つ場合、左側の子ノードまでの深さをreturnして右側の子ノードの深さは調べずに処理が終わりそうだけど良いのかと気になった。

→今回の問題は葉ノードまでの最短距離を求めるので、最初に葉に達した時点でその深さを返せば良いので問題なしということ？

解答2：深さ優先探索

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        #木がない場合(葉ノード)
        if not root:
            return 0
        #左右いずれかの子ノードがない場合
        #子ノードが1つでもあると葉ノードではないため、深い方を返す
        elif root.left is None or root.right is None:
            left = self.minDepth(root.left)
            right = self.minDepth(root.right)
            #深い方(子ノードがある方)を返す
            return max(left, right) + 1
        #左右どちらも子ノードがある場合
        #else:
        elif root.left and root.right:
            left = self.minDepth(root.left)
            right = self.minDepth(root.right)
            #浅い方の深さを返す
            return min(left, right) + 1

class Solution:

def minDepth(self, root: Optional[TreeNode]) -> int:

#木がない場合(葉ノード)

if not root:

return 0

#左右いずれかの子ノードがない場合

#子ノードが1つでもあると葉ノードではないため、深い方を返す

elif root.left is None or root.right is None:

left = self.minDepth(root.left)

right = self.minDepth(root.right)

#深い方(子ノードがある方)を返す

return max(left, right) + 1

#左右どちらも子ノードがある場合

#else:

elif root.left and root.right:

left = self.minDepth(root.left)

right = self.minDepth(root.right)

#浅い方の深さを返す

return min(left, right) + 1

補足・参考・感想

参考

前：110. Balanced Binary Tree

次：112. Path Sum

LeetCode 解答・解説記事一覧