使用yield递归搜索树获取根到目标节点父节点列表遇栈溢出问题

原代码的核心问题 #

1. 逻辑错误：仅在当前节点等于目标时返回该节点，子节点找到目标时不会将当前父节点加入结果集，无法生成从根到目标的完整路径。
2. 无终止遍历：找到目标后仍会递归遍历当前节点的其他子节点，导致大量不必要的递归调用，即使树规模小也可能触发StackOverflowException。
3. 结果顺序颠倒：即使修正路径逻辑，原代码返回的序列是从目标到根，不符合需求的根到目标顺序。

修正后的实现（基于Yield语法） #

IEnumerable<Node> GetParentsToTarget(Node parent, Node target)
{
    // 当前节点即为目标，返回自身并终止后续遍历
    if (parent == target)
    {
        yield return parent;
        yield break;
    }

    foreach (var child in parent.Nodes)
    {
        // 提前获取子节点的路径（避免多次枚举递归结果）
        var childPath = GetParentsToTarget(child, target).ToList();
        
        if (childPath.Any())
        {
            // 先返回当前父节点，再追加子节点的路径
            yield return parent;
            foreach (var node in childPath)
            {
                yield return node;
            }
            // 找到目标后终止遍历其他子节点，减少递归开销
            yield break;
        }
    }

    // 未找到目标，返回空序列
    yield break;
}

关键改进点 #

• 路径构建逻辑：当子节点分支找到目标时，先将当前父节点加入结果，再追加子节点的路径，保证序列顺序为根→目标。
• 提前终止遍历：找到目标后立即终止当前节点的子节点遍历，避免无意义的递归调用，从根源减少栈溢出风险。
• 延迟枚举优化：用ToList()提前获取子节点路径，避免多次枚举递归生成的序列（多次枚举会重复执行递归逻辑，加剧栈压力）。

验证示例结果 #

• GetParentsToTarget(ROOT, K) → 返回 {ROOT, H, I, K}
• GetParentsToTarget(A, G) → 返回 {A, E, G}
• GetParentsToTarget(A, K) → 返回 {}（K不在A的子树中）

内容的提问来源于stack exchange，提问作者mike