在寻找任意嵌套列表的最大深度

Question

我目前正在使用Python中的递归函数,而且我遇到了问题.标题是,问题是返回任意嵌套列表的最大深度.

这是我到目前为止:

def depthCount(lst):
    'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.'

    var = 0

    if len(lst) > 0:

        if type(lst[0]) == list:
            var += 1
            depthCount(lst[1:])

        else:
            depthCount(lst[1:])

    else:
        return var

我觉得问题出在我的递归调用上(这可能很明显).当列表到达结尾时它确实会返回var,但是当我有一个非空列表时,事情就会出错.什么都没有归还.

我切错了吗？我应该在递归调用中的切片之前做些什么吗？

问题也可能出在我的基本案例中.

Answer 1

如果它们只是嵌套列表,例如[[[], []], [], [[]]],这是一个很好的解决方案:

def depthCount(lst):
    return 1 + max(map(depthCount, lst), default=0)

如果您不使用Python 3.4,那么您可以使用以下default参数:

def depthCount(lst):
    return len(lst) and 1 + max(map(depthCount, lst))

他们的数量也不同.第一个将空列表视为深度1,第二个认为深度为0.第一个很容易适应,但是,只需将默认值设为-1.

如果它们不仅仅是嵌套列表,例如,以下[[[1], 'a', [-5.5]], [(6,3)], [['hi']]])是对它的适应性:

def depthCount(x):
    return 1 + max(map(depthCount, x)) if x and isinstance(x, list) else 0

def depthCount(x):
    return int(isinstance(x, list)) and len(x) and 1 + max(map(depthCount, x))

确保你了解后者是如何工作的.如果你还不知道它,它会教你如何and使用Python :-)

采取"纯粹递归"的挑战:

def depthCount(x, depth=0):
    if not x or not isinstance(x, list):
        return depth
    return max(depthCount(x[0], depth+1),
               depthCount(x[1:], depth))

当然,额外的论点有点难看,但我认为没关系.

Answer 2

因此，本质上，您所指的数据结构是k 叉树，也称为 n 叉树，具有任意分支。这是确定最大值的代码。具有任意分支的 n 叉树的深度。

def maxdepth(tree):
    if isleaf(tree):
        return 1
    maximum = 0
    for child in children(tree):
        depth = maxdepth(child)
        if depth > maximum:
            maximum = depth
    return maximum + 1

您可以在此处查看使用不同测试输入运行的代码。