python - 在二叉搜索树中打印最大深度

Question

我正在尝试获得二叉搜索树的最大深度，但是我相信这棵树的计数是错误的。

我的代码：

    def BST_maxdepth(root):
        curdepth = [1]
        maxdepth = [1]
        if root is None:
            return -1
        else:
            curdepth[0] = 1
            maxdepth[0] = 1
            if root.left is not None or root.right is not None:
                curdepth[0] += 1
                if curdepth[0] > maxdepth[0]:
                    maxdepth[0] = curdepth[0]
                BST_maxdepth(root.left)
                BST_maxdepth(root.right)
        return maxdepth[0]

类和 BST：

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


def BST_Insert(root, node):     # root --> root of tree or subtree!
    if root.value is None:
        root = node             # beginning of tree
    else:
        if root.value > node.value:     # go to left
            if root.left is None:
                root.left = node
            else:
                BST_Insert(root.left, node)

        if root.value < node.value:    # go to right
            if root.right is None:
                root.right = node
            else:
                BST_Insert(root.right, node)

测试：

r = Node(8)


a = Node(5)
b = Node(2)
c = Node(1)
d = Node(3)
e = Node(7)

输出：

2

预期输出：

4

Answer 1

为什么不像...

def BST_maxdepth(root, depth=0):
    if root is None:
        return depth
    return max(BST_maxdepth(root.left, depth+1),
               BST_maxdepth(root.right, depth+1))

Answer 2

您不会maxdepth多次更新。也许是这样的：

left_depth = BST_maxdepth(root.left)
right_depth = BST_maxdepth(root.right)
maxdepth[0] = max(left_depth, right_depth) + 1

Answer 3

curdepth当你递归时，你并没有随身携带maxdepth，而且它们不是全球性的。在每次调用 时BST_maxdepth，您声明一个新的curdepthand maxdepth。

这意味着无论您的树有多深，maxdepth都只会是 2（如果根没有孩子，则为 1）。

您可以尝试使用累加器，或者从每个递归调用中返回一个值并maxdepth以这种方式构建。

Answer 4

您maxdepth的每个递归步骤都不会传递给父步骤。

信息来自

BST_maxdepth(root.left)
BST_maxdepth(root.right)

需要返还给父母。

您正在搜索的每个级别重新实例化它们：

 curdepth = [1]
 maxdepth = [1]