如何在JSON dict of tree上用递归函数实现DFS？

Question

我使用递归深度优先搜索函数遍历树，其中每个节点都有一个索引。

在遍历过程中，我需要将一个节点（类型为dict）分配给一个变量，以便从外部范围进一步处理。

看来我使用了无用的赋值。最有效的方法是什么？

def dfs(json_tree, index, result):
    if json_tree['index'] == index:
        result = json_tree['index']   ## not work!
        return
    if 'children' not in json_tree:
        return
    for c in json_tree['children']:
        dfs(c, index, result)

Answer 1

尝试 returning 结果。请注意，我更改了您的函数签名。一旦找到索引，这也会使搜索短路。

def dfs(json_tree, index):
    if json_tree['index'] == index:
        return json_tree['index']
    if 'children' not in json_tree:
        return None
    for c in json_tree['children']:
        result = dfs(c, index)
        if result is not None:
            return result
    return None

编辑：更新了最终 return 路径，以防找不到索引。