面试题：Python递归函数在复杂数据结构遍历中的应用及性能分析

Question

给定一个嵌套的字典结构，例如 {'a': 1, 'b': {'c': 2, 'd': {'e': 3}}}, 编写一个递归函数来遍历这个字典，收集所有叶子节点的值。并且分析该递归函数在不同规模的嵌套字典下的时间和空间复杂度。

Answer 1

def collect_leaf_values(dictionary):
    result = []
    for key, value in dictionary.items():
        if isinstance(value, dict):
            result.extend(collect_leaf_values(value))
        else:
            result.append(value)
    return result

时间复杂度分析

假设字典中总共有 $n$ 个键值对。对于每个键值对，在最坏情况下，每次递归调用都需要遍历当前字典中的所有键值对。所以，时间复杂度为 $O(n)$。这是因为每个键值对最多被访问一次。

空间复杂度分析

1. 递归调用栈空间：在最坏情况下，嵌套字典是一条链状结构，递归深度等于嵌套层数。假设嵌套层数为 $d$，递归调用栈的深度为 $O(d)$。
2. 存储结果的空间：假设叶子节点的数量为 $l$，存储结果的空间为 $O(l)$。

综合起来，空间复杂度为 $O(d + l)$。在最坏情况下，当所有节点都是叶子节点时，$l = n$，空间复杂度为 $O(n)$；当嵌套层数最大时，$d$ 接近 $n$，空间复杂度也为 $O(n)$。