深度优先搜索没有返回正确的对象类型

Question

我有下面的代码，它遍历一个树对象，但是我无法使它在找到键时返回节点对象。它给我NoneType。对象很简单，包含在下面。

class StructureTree:
    def __init__(self, issueID, depth):
        self.issueID = issueID
        self.depth = depth
        self.children = []
        self.worklog_data_rows = []
        self.structure_data_row = [] #contains issue data for any issue found in the global structure

    def addChild(self, elem):
        self.children += [elem]
    def __repr__(self):
        return "<%d : %d>" % (self.issueID, self.depth)

class StructureForest:
    def __init__(self):
        self.trees = []
        self.roots =[]
    def addRoot(self, root):
        self.roots += [root]
def DFS(node, key):
'''
Depth First Traversal (In-order).
@node -- int
@key -- int
'''
    if node.issueID == key:
        print "Found!"
        return node
    else:
        for child in node.children:
            print "here"
            return DFS(child, key)

def search_node(n_tree_forest, key):
'''
Traverses entire forest.
@key -- int
'''
    for root in n_tree_forest.roots:
       val = DFS(root, key)
       return val

Answer 1

无论在主函数中还是在任何递归步骤中，都不会返回值。两次调用DFS都需要调用return DFS(..., ...)

Answer 2

嗨，我想我看到这个问题看起来不像你返回任何东西，当你进入else语句，你必须做适当的递归。修改你的DFS方法…

def DFS(node, key):
    if node.issueID == key:
        print "Found!"
        return node.issueID
    else:
        for child in node.children:
            print "here"
            val = DFS(child, key)
            if val: return val
         return False