我如何找到二叉树内特定节点的深度？

Question

我正在尝试找出此问题的递归解决方案。最主要的是返回节点所在的二叉树中的级别。

def find_depth(tree, node):
    if node == None:
        return 0 
    else: 
        return max(find_depth(tree.left))
        #recursive solution here 

使用此类的值：

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

示例：调用find_depth（tree，7）应该返回树中7的级别。 （第2级）

   3
  / \
  7  1  <------ return that 7 is at level 2
 / \  
 9 3   

Answer 1

也许这就是您想要的

    def find_depth(tree, node):
        if node is None or tree is None:
            return 0

        if tree == node:
            return 1

        left = find_depth(tree.left, node)
        if left != 0:
            return 1 + left
        right = find_depth(tree.right, node)
        if right != 0:
            return 1 + right

        return 0

Answer 2

您需要在find_depth通话中提供有关深度的信息。它可能看起来像这样（假设0是一个通知消息，通知未找到该节点）：

def find_depth(tree, node, depth=1):
    if node == None:
        return 0

    if tree.value == node:
        return depth

    left_depth = find_depth(tree.left, node, depth+1)
    right_depth = find_depth(tree.right, node, depth+1)
    return max(left_depth, right_depth)

然后您用两个参数调用它：x = find_depth(tree, 7)。