値のバイナリ検索ツリーを持つ特定のノードの深さを返します

Question

私の問題は、ツリー内にvalueというノードの深度を返すように求めています。私はdepth(root, 7, 0 [depth initially])をしなかった場合

例えば、それは2

私の最初の試みを返す必要があり、私はこの

# value is the value wanted, count measures the 'depth' 

def depth(root, value, count): 

    # if we are not at a empty node 
    if root != None: 
     # if we found our data, then just return the count (depth) 
     if root.data == value: 
      return count 


     # otherwise increase count, and traverse both sides 
     else: 
      count += 1 
      count = depth(root.left, value, count) 
      count = depth(root.right, value, count) 


    return count 

のようなもの、私は深さを得るのに、私はこれを実行しました= 6、なぜ私は分かりません

Answer 1

枝の2番目の部分では、必要な時に戻ってきません。

rootで目標値が見つからないとします。次に、左に検索した結果にcountを設定します。次に、左（再び）を検索した結果にcountを設定します。

あなたは決して権利を検索せず、あなたがターゲットを見つけたかどうか（ifから落ちた後）カウントを返します。今すぐあなたの戻り値は、ターゲットが見つかったとき、またはcount「ターゲットを見つけることができなかった」という意味、Noneのどちらかになります

if you match the target: 
    return count 
else: 
    search on the left side. 
    if that is not None, return it. 
    search on the right side. 
    regardless of whether it's None or not, return it. 

：

より良いアプローチは、になります。途中ダウンの

Answer 2

なぜcountときにできる方法バックアップのcount：

def depth(root, value): 
    # if we are at a empty node return infinity 
    if not root: 
     return float('inf') 

    # if we found our data, then just return 0 
    if root.data == value: 
     return 0 
    # otherwise traverse both sides 
    return 1 + min(depth(root.left, value), depth(root.right, value)) 

は、あなたがあなたの端子ケースとしてreturn Noneして、チェックを実装することができますmin()を取り除くために、それは醜いですし、慣用ない：

：

def depth(root, value): 
    # if we are at a empty node return None 
    if not root: 
     return None 

    # if we found our data, then just return 0 
    if root.data == value: 
     return 0 

    # otherwise, traverse both sides 
    c = depth(root.left, value) 
    if c is None: 
     c = depth(root.right, value) 
     if c is None: 
      return None 
    return c + 1 

またBFSとしてそれを実装