質問する

Approach 1. DFS recursively

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:						[1]
             return 0
        if not root.left and not root.right:			[2]
            return 1
        if not root.left:					[3]
            return self.minDepth(root.right) + 1
        if not root.right:					[4]
            return self.minDepth(root.left) + 1
            
        return min(self.minDepth(root.right),\
        self.minDepth(root.left)) + 1				[5]

上の方法は私が最初に解読した方法です.DFSは反復式と再帰式の2種類に分けられる.反復解はBFSを適用する方法と似ているが,書き込みキューの代わりにスタックを用いる点がある.
そこで再帰コードを書いてみました.
[1]再帰またはbasecaseが必要です.最初のbasecaseは最上位ノードrootがNoneです.0を返します.
[2]2番目のbasecaseはルートの両側がNoneの場合である.では根だけの木なので奥行きは1.は、1を返します.
[3]今から再帰します.rootの左側がNoneで、rootの右側がNoneでない場合はminDepthを呼び出します.
minDepthが返す深さの値に1を加算します.
1を追加しない場合は、前のノードの深さのみが計算されるため、値を更新するには1を追加する必要があります.
[4]ルートの右側がNoneで、ルートの左側がNoneでない場合、minDepthが呼び出され、minDepthが返す深度値に1が加算される.
[5]根の左右の2つがある場合、この2つのうち1つの値が小さいものを選択し、もう1つ追加する.
例の入力として、適切な場所にルートディレクトリを入力します.valとconditionが印刷されました.
input: [3,9,20,null,null,15,7]
stdout:

=======================================
root is  3
root has both children
=======================================
root is  20
root has both children
=======================================
root is  7
root has no children
=======================================
root is  15
root has no children
=======================================
root is  9
root has no children

予想される順序で3,20,7,15,9を順に探索することが見られる.まず最下端7に到達する.

Approach 2. BFS

class Solution:
    def minDepth(self, root:TreeNode) -> int:
        if not root:					[3]
            return 0
        q = collections.deque() 			[1]
        q.append((root,1))				[2]
        
        while q:					[4]
            node, depth = q.popleft()			[5]
            if not node.left and not node.right:	[6]
                return depth
            if node.left:				[7]
                q.append((node.left, depth+1))
            if node.right:				[8]
                q.append((node.right, depth+1))

[1]ツリーを保存するためにcollectionというモジュールからdequeを取得する.
[2]ツリーと奥行き1を最初に保存します.根が1つあれば、深さは1になるからです.ルートがNoneの場合、最初の行[3]で保留して0を返します.
[4]qが空でないまでwhile loopを回します.
[5]まずpopleftによりqに格納されたノードと深さを取得する.
[6]ノードの左、右がNone(つまりノードが木の最下部)であれば、深さを返す
[7]ノードの左側のみ(右側がNone)の場合、ノードの左側のサブツリーはqに保存され、深さは+1となり、ハッシュ値によって更新される
[8][7]と同様に,ノードの右側のみであれば右側サブツリーを保存し,深さ+1に更新する.
[6]時にwhile loopから値を返す!
例の入力として、適切な場所にルートディレクトリを入力します.valとconditionが印刷されました.
input: [3,9,20,null,null,15,7]
stdout:

=================================
node is  3
depth:  1
=================================
node has left child
=================================
node has right child
=================================
node is  9
depth:  2
=================================
node has no children

比較

次はDFS、上はBFS解読の結果です.
DFSは、必要な時間とメモリから、より長い時間が必要であることがわかります.なぜなら、この問題は最大深さではなく、最小深さを求めるからだ.ターゲットは存在しないサブノードを探し,ルートからノードへの深さを求めるため,隣接ノードからのナビゲーションがより速くなる.一番下のノードまで行く理由がないからです.