时间戳

首页 > 解决方案 > 如何找到树的最大深度？

python - 如何找到树的最大深度？

问题描述

我有一个树数据结构，定义如下：

class Tree(object):
    def __init__(self, name='ROOT', children=None):
        self.name = name
        self.children = []
        if children is not None:
            for child in children:
                self.add_child(child)
    def __repr__(self):
        return self.name
    def add_child(self, node):
        assert isinstance(node, Tree)
        self.children.append(node)

我需要编写一个函数来查找树的深度。这是我编写的函数（以 Tree 作为输入，并返回一个整数值作为输出），但它没有给出正确的答案：

def depth(tree): 
    count = 1
    if len(tree.children) > 0:
        for child in tree.children:
            count = count + 1
            depth(child)
    return count

我该如何纠正？

标签： pythontree

解决方案

虽然您depth(child)确实进行了递归调用，但它对返回值（深度）没有任何作用。您似乎只是简单地计算给定级别的节点并称其为深度（实际上是宽度）。

您需要的是（伪代码）：

def maxDepth(node):
    # No children means depth zero below.

    if len(node.children) == 0:
        return 0

    # Otherwise get deepest child recursively.

    deepestChild = 0
    for each child in node.children:
        childDepth = maxDepth(child)
        if childDepth > deepestChild:
            deepestChild = childDepth

   # Depth of this node is one plus the deepest child.

   return 1 + deepestChild

推荐阅读