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

この記事は約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, 105].
  • -1000 <= Node.val <= 1000

 

内容

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

 

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

方針

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

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

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

解答

解答1:幅優先探索

 

[1]

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

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

 

 

 

解答2:深さ優先探索

 

 

 

補足・参考・感想

参考

 

 

前:110. Balanced Binary Tree

次:112. Path Sum

LeetCode 解答・解説記事一覧

コメント