使用值二进制搜索树返回特定节点的深度。

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.

现在，您的返回值将是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