返回值为二值搜索树的特定节点的深度

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