Рекурсивно повторять вложенный dict и возвращать значение первого соответствующего ключа

Question

У меня есть глубоко вложенный dict, и мне нужно пройти через него и вернуть значение, соответствующее аргументу key, второму аргументу моей функции.

Например, с

tree = {"a": 12, "g":{ "b": 2, "c": 4}, "d":5}

tree_traverse(tree, "d") должен вернуть 5

Вот мой код:

def tree_traverse(tree, key):
    for k,v  in tree.items():
        if isinstance(v, dict):
            tree_traverse(v, key)

        elif k == key:
            return v

Проблема, с которой я столкнулся, заключается в том, что эта функция возвращает None, если она не находит соответствующий ключ после того, как она выполнит итерацию по самому глубокому вложенному dict. Я не хочу, чтобы он что-либо возвращал, пока не найден соответствующий ключ.

Я не нашел решения в другом потоке, большинство из них используют операторы print и ничего не возвращают, поэтому я полагаю, что это позволяет избежать этой проблемы.

Answer 1

Здесь мы создаем объект при создании функции, которым будут делиться все исполнения функции, который называется _marker. Мы возвращаем этот объект, если не найдем ключ. (Вы также можете использовать None здесь, но None часто является значимым значением.)

def tree_traverse(tree, key, *, _marker=object()):
    for k,v  in tree.items():
        if isinstance(v, dict):
            res = tree_traverse(v, key, _marker=_marker)
            if res is not _marker:
                return res
        elif k == key:
            return v
    return _marker

def find(tree, key):
    _marker = object()
    res = tree_traverse(tree, key, _marker=_marker)
    if res is _marker:
        raise KeyError("Key {} not found".format(key))
    return res

Я использую tree_traverse в качестве вспомогательной функции, потому что мы хотим, чтобы поведение на внешнем слое нашей рекурсии отличалось от того, которое мы хотим внутри (вернуть _marker объект)

Answer 2

Вы должны проверить, действительно ли рекурсивный вызов что-то нашел, чтобы вы могли продолжить цикл. Например. попробуйте следующее:

def tree_traverse(tree, key):
    for k, v  in tree.items():
        if k == key:
            return v
        elif isinstance(v, dict):
            found = tree_traverse(v, key) 
            if found is not None:  # check if recursive call found it
                return found