主页 / 问题 / 981699
Accepted
vladionair
Asked:2020-05-15 18:59:28 +0000 UTC2020-05-15 18:59:28 +0000 UTC

遍历树时使用递归

  • 772

问题是这样的：如果我在递归函数调用之前指定返回：return find(node, counter)- 它过早终止，跳过树的第一个分支。如果我没有指定：find(node, counter)- 遍历所有节点，但不返回计数器。如何遍历整棵树？

def Count(self):
    if not self.Root:
        return 0
    tree = self.Root
    counter = 1
    def find(tree, counter):
        for node in tree.Children:
            counter += 1
            if node.Children:
                return find(node, counter) # this place
        return counter
    count = find(tree, counter)
    return count
python

2 个回答

  1. ...通过以下方式解决了这种情况。只是改变了柜台的本质......

        def Count(self):
        if not self.Root:
            return 0
        tree = self.Root
        counter = [1]
        def find(tree, counter):
            for node in tree.Children:
                counter[0] += 1
                print(node.NodeValue)
                if node.Children:
                    find(node, counter)
            return counter
        count = find(tree, counter)
        return count[0]
    • 1
  2. Best Answer

    要编写递归函数，您需要递归思考：）

    假设我们已经有一个正确的函数find来满足我们的需要——它计算从某个根开始的节点数。

    然后对于当前节点，我们需要计算所有子节点的节点数，find为每个子节点调用，并且还要在这个总和上加一——当前节点。

    def Count(self):
    def find(tree):
        return 1 + sum(find(node) for node in tree.Children)

    return 0 if self.Root is None else find(self.Root)
    • 1

相关问题