값 이진 검색 트리가있는 특정 노드의 깊이를 반환

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

브랜치의 두 번째 부분에서해야 할 때 다시 돌아 오지 않을 것입니다.

root에서 대상 값을 찾지 못했다고 가정 해보십시오. 그런 다음 왼쪽으로 검색 한 결과에 대해 개수를 설정합니다. 그런 다음 왼쪽 (다시) 검색 결과에 개수를 설정합니다.

당신은 결코 오른쪽을 검색하지 않으며, 당신은 목표를 찾았는지 아닌지 (if에서 빠져 나온 후에) 카운트를 반환합니다.

이

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. 

이제 반환 값 중 하나 대상이 발견 된 경우, 또는 count "대상을 찾을 수 없습니다"의미 None 될 것입니다 :에

더 좋은 방법이 될 것입니다. 길 아래에

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로 구현