将根从嵌套的字典树返回到特定叶 [英] Return root to specific leaf from a nested dictionary tree

问题描述

嵌套的字典树的形式为

categories = [{
    'name': 'Cat1',
    'children': [{
        'name': 'SubCat1',
        'children': [{
            'name': 'SubSubCat1',
            'children': []
         }]
     }]
}, {
    'name': 'Cat2',
    'children': []
}]

递归函数应该返回从根到特定叶子的路径.

The recursive function should return the path from root to a specific leaf.

让我们说，function(categories, 'SubCat1')应该返回一个包含['Cat1', 'SubCat1']的列表.同样，对于function(categories, 'Cat2')，应返回['Cat2'].

Lets say, function(categories, 'SubCat1') should return a list containing ['Cat1', 'SubCat1']. Likewise for function(categories, 'Cat2') should return the ['Cat2'].

到目前为止取得的进展

def recurse_category(categories, to_find):
    def _recurse_category(categories, to_find, path=[]):
        for category in categories:
            path.append(category['name'])
            if len(category['children']) == 0 and category['name'] != to_find:
                return path, False

            if category['name'] == to_find:
                return path, True
            else:
                recurse_category(
                    category['children'], to_find, path
                )
    return _recurse_category(categories, to_find, path=[])

推荐答案

不要传递列表；它将累积所有搜索的路径，而不仅仅是匹配的路径.通过连接建立递归列表.您还需要处理递归调用的结果.您的代码将忽略该结果.

Don't pass along a list; it'll accumulate all searched paths, not just the one that matches. Build up the list as you recurse, by concatenating. You also need to process the result of the recursive call; your code ignores that result.

以下工作原理，请注意，当我们递归(在if category['children']中)时，代码必须检查是否在该子树中找到了路径:

The following works, note that when we recurse (in if category['children']) the code has to check if a path was found in that subtree:

def recurse_category(categories, to_find):
    for category in categories:
        if category['name'] == to_find:
            return True, [category['name']]
        if category['children']:
            found, path = recurse_category(category['children'], to_find)
            if found:
                return True, [category['name']] + path
    return False, []

这将返回一个布尔值(如果找到，则为true)和路径:

This returns a boolean (true if found) and the path:

>>> recurse_category(categories, 'SubCat1')
(True, ['Cat1', 'SubCat1'])
>>> recurse_category(categories, 'Cat2')
(True, ['Cat2'])
>>> recurse_category(categories, 'Nonesuch')
(False, [])

这篇关于将根从嵌套的字典树返回到特定叶的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！