在根树型有向无环图中判定是否存在长度为N的路径的线性时间算法

嘿，你的思路方向是对的，但我们可以做一些优化，让算法严格满足线性时间O(V+E)（因为树的E=V-1，所以实际是O(V)），同时避免不必要的空间开销。

先明确你的问题前提：这是一棵外向根树（所有边从父节点指向子节点，根出发的路径互不相交——其实这个条件本质是树中任意两个路径要么完全分离，要么是包含关系，也就是标准的树结构特性），我们需要判断是否存在一条路径（边的长度之和为N）。

最优线性时间解法：利用祖先-后代路径的长度特性 #

树中的任意路径都是从某个祖先节点到其后代节点的简单路径，这意味着：
如果我们计算每个节点u到根节点的路径总长度为d[u]，那么路径u → v（u是v的祖先）的长度就是d[v] - d[u]。

基于这个特性，我们可以用深度优先搜索（DFS）+ 哈希集合来快速判断，以下是伪代码实现：

def has_path_of_length_N(root, target_N):
    # 存储遍历过程中遇到的节点到根的路径长度
    visited_lengths = set()
    visited_lengths.add(0)  # 根节点到自己的长度为0

    def dfs(current_node, current_total):
        for child_node, edge_length in current_node.children.items():
            # 计算子节点到根的总长度
            child_total = current_total + edge_length
            # 检查是否存在祖先节点，使得路径长度等于target_N
            if (child_total - target_N) in visited_lengths:
                return True
            # 将当前子节点的长度加入集合，供后续节点检查
            visited_lengths.add(child_total)
            # 递归遍历子节点
            if dfs(child_node, child_total):
                return True
            # 回溯：移除当前子节点的长度，避免影响其他分支
            visited_lengths.remove(child_total)
        # 当前节点的所有子节点都遍历完，未找到符合条件的路径
        return False

    return dfs(root, 0)

这个方法的时间复杂度是O(V)，因为每个节点仅被访问一次，哈希集合的增删查操作平均是O(1)；空间复杂度是O(V)（最坏情况是链状树，集合中最多存储V个元素）。

对你原有思路的优化 #

你提到的“拓扑序遍历+记录每个顶点出发的路径”思路是可行的，但如果直接记录所有路径长度，空间会随路径数量爆炸（比如多叉树中每个节点有大量子路径）。我们可以对这个思路做剪枝优化：

• 采用后序遍历（属于拓扑序的一种，从叶子到根），对每个节点u，只需要记录从u出发的所有路径长度，但一旦发现某个长度等于N，直接终止算法返回结果。
• 同时对每个节点的路径长度集合去重，减少后续子节点的计算量（比如两个子节点都能得到长度l，那么u只需要保留一个l即可）。

不过这种方法在最坏情况下（比如链状树）的时间空间和上面的DFS方法一致，但哈希集合的方法更简洁高效，且不需要维护每个节点的路径长度集合。

举个简单例子 #

假设树结构是：
root（到根长度0）→ A（边长度2，到根长度2）→ B（边长度3，到根长度5）
我们要找目标长度N=3的路径：

1. 遍历到A时，检查2-3=-1不在集合（集合里有0），把2加入集合。
2. 遍历到B时，检查5-3=2在集合里（集合里有0,2），说明路径A→B的长度是3，符合条件，直接返回存在。

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