python - 如何找到二叉树中特定节点的深度？

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