返回值爲二值搜索樹的特定節點的深度

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 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. 

現在你的返回值要麼是None，意思是「找不到對象」，或count當發現目標。

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)) 

爲了擺脫min()那麼你可以return None作爲終端的情況下，然後實施檢查，但它是醜陋不地道：

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：

def depth(root, value): 
    q = [(root, 0)] 
    while q: 
     node, depth = q.pop(0) 
     if node.data == value: 
      return depth 
     depth += 1 
     if node.left: 
      q.append((node.left, depth)) 
     if node.right: 
      q.append((node.right, depth)) 
    return None