使用递归法求树中特定节点的深度

Question

我正在尝试解决一个问题，我返回一个数字出现在树中的最大深度。例如，如果树是这样的：

    1
  /   \
2      3
        \
         2

我的函数应该返回2。但是，我的函数返回0

^{pr2}$

我的思维过程是不是错了？如果当前值与我要查找的值（即参数）匹配，我应该添加1，如果它们不匹配，则不添加1。我使用max()所以它返回左子元素或右子元素的最大值，所以我得到深度更高的子元素。错了吗？在

以下是树类：

class TN:
    def __init__(self,value,left=None,right=None):
        self.value = value
        self.left  = left
        self.right = right

这是我对树的构造：

tree4 = TN(2)
tree3 = TN(3, left = None, right = tree4)
tree2 = TN(2)
tree1 = TN(1, left = tree2, right = tree3)
print(max_depth(tree1, 2))

将打印0

Answer 1

我认为这是一个很好的max_depth编码

我们添加一个附加参数d，默认值为0。此参数用于跟踪当前深度。当返回一个答案时，我们只在节点t值匹配时在max (d, ...)中包含d，否则，我们返回left和right结果的最大值

def max_depth (t, value, d = 0):
  if t is None:
    return -1
  elif t.value == value:
    return max ( d
               , max_depth (t.left, value, d + 1)
               , max_depth (t.right, value, d + 1)
               )
  else:
    return max ( max_depth (t.left, value, d + 1)
               , max_depth (t.right, value, d + 1)
               )

这是你问题中的代码树

^{pr2}$

找到每个值的最大深度

print (max_depth (tree, 1))
# 0

print (max_depth (tree, 2))
# 2

print (max_depth (tree, 3))
# 1

如果找不到该值，将返回-1

print (max_depth (tree, 4))
# -1

Answer 2

如果我没弄错的话，你要解决的问题是：树中value值的最大深度是多少。

您不仅应该在t.value == value时增加计数，而且还应该在树的任何子代与您要查找的值匹配时增加计数。这是因为你在测量深度。在

以下是算法的外观：

def max_depth(t,value):
    if t == None:
        return -1
    left = max_depth(t.left, value)
    right = max_depth(t.right, value)
    if t.value == value or left > -1 or right > -1: # <<<<
        return 1 + max(left,right)
    else:
        return max(left,right) # This is always -1