面试题：Python for循环中的生成器与迭代器深度应用

Question

给定一个复杂的树形数据结构，节点存储了一些数值。请使用生成器和for循环来实现一个函数，该函数能够以深度优先遍历的方式，按照节点的特定属性（例如节点权重从小到大）来遍历整个树，并返回遍历结果。请详细说明你的设计思路以及核心代码实现。

Answer 1

设计思路

1. 首先，使用生成器来实现深度优先遍历。生成器的好处是可以按需生成数据，而不是一次性加载所有数据到内存，适合处理大型树形结构。
2. 为了按照节点的特定属性（如节点权重从小到大）遍历，在生成器生成节点时，将所有子节点按照该属性排序，然后依次递归处理。
3. 使用for循环来迭代生成器，获取遍历结果。

核心代码实现（以Python为例）

class TreeNode:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.children = []


def dfs_generator(root):
    stack = [root]
    while stack:
        node = stack.pop()
        yield node
        # 按照权重从小到大排序
        node.children.sort(key=lambda x: x.weight)
        stack.extend(node.children[::-1])


def traverse_tree(root):
    result = []
    for node in dfs_generator(root):
        result.append(node.value)
    return result


# 示例用法
root = TreeNode(1, 3)
root.children.append(TreeNode(2, 1))
root.children.append(TreeNode(3, 2))

print(traverse_tree(root))

上述代码首先定义了一个TreeNode类来表示树的节点，包含节点的值和权重，以及子节点列表。dfs_generator函数使用栈实现深度优先遍历，并按照节点权重排序子节点。traverse_tree函数使用for循环迭代生成器，将节点值收集到结果列表中并返回。