如何递归遍历树并在python中创建已访问节点的列表

Question

我定义了一个类树，它由树节点列表组成，如下所示：

class Tree(object):
    def __init__(self, name, nodes):
        self.name = name
        self.nodes = nodes

class TreeNode(object):
    def __init__(self, name, parent):
        self.name = name
        self.parent = parent

如您所见，对于每个TreeNode，我只定义一个父节点。但是，我想写一个树方法，它给我一个名为targetNodeName的目标节点的所有父节点的列表（输出列表还应该包括targetNodeName本身）。为此，我编写了一个递归函数，该函数在构建一个名为results的列表时迭代，直到找到没有父节点的节点（即根节点）。在

^{pr2}$

但是我的递归函数并没有按预期的那样运行。我举了一个例子，我首先定义了一个三层的7节点树，然后调用allParents方法来获取节点“N7”的所有父节点，即['N7'，'N3'，'N1']。在

# create nodes
myTreeNodes = []
myTreeNodes.append(TreeNode(name = 'N1', parent = None))
myTreeNodes.append(TreeNode(name = 'N2', parent = 'N1'))
myTreeNodes.append(TreeNode(name = 'N3', parent = 'N1'))
myTreeNodes.append(TreeNode(name = 'N4', parent = 'N2'))
myTreeNodes.append(TreeNode(name = 'N5', parent = 'N2'))
myTreeNodes.append(TreeNode(name = 'N6', parent = 'N3'))
myTreeNodes.append(TreeNode(name = 'N7', parent = 'N3'))

myTree = Tree(name = 'ST1', nodes = myTreeNodes)

a = myTree.allParents(targetNodeName = 'N7', results = [])
print a

> ['N7', 'N3', 'N1']
> None

尽管它打印出正确的父节点列表-请注意函数中的“debug”print命令-（即['N7'，'N3'，'N1']），但该函数返回None，这意味着我被从函数中删除，没有返回任何内容。我该怎么解决这个问题？在

Answer 1

使用is检查值是否等于None。 allParents方法可以简化为：

def allParents(self, targetNodeName):
    currentNode = next(node for node in self.nodes
                       if node.name == targetNodeName)
    if currentNode.parent is None:
        return [currentNode.name]
    else:
        return [currentNode.name] + self.allParents(currentNode.parent)

Answer 2

使用debugger单步执行该方法对于确定代码采用的路径非常有帮助。在

使用这个方法，我可以看到该方法最初跟随else分支，只有对self.allParents的子调用才导致print语句。问题在于results.append，它总是返回None，而不是列表。在

a = []
b = a.append(3)
assert a == [3]
assert b is None

最简单的解决方案是将行拆分为原始的results.append，然后是{}。在