树递归：如何在深度优先搜索(DFS)中加入条件查找全激活节点路径

核心过滤逻辑插入规则 #

你只需要在DFS遍历的节点访问起始阶段插入状态校验逻辑即可，具体执行流程如下：

• 访问任意节点时，首先校验状态：如果是未激活（红色），直接终止当前分支遍历，不需要向下递归子节点，当前分支直接判定为无效。
• 如果节点为激活（绿色），先将其加入当前路径记录，再判断是否为叶子节点：
  • 是叶子节点：直接返回当前记录的路径，即为符合要求的根到叶全激活路径
  • 非叶子节点：依次递归遍历所有子节点
• 若当前节点的所有子节点遍历完成后都未找到有效路径，将当前节点从路径记录中移除（回溯操作），回到上层节点继续遍历其他分支。

参考伪代码实现 #

# 入参说明：
# current_node: 当前遍历的节点，包含status（激活状态）、children（子节点列表）两个属性
# current_path: 记录当前遍历路径的列表
def find_valid_path(current_node, current_path):
    # 过滤未激活节点，当前分支无效
    if current_node.status != "激活":
        return None
    # 有效节点加入路径
    current_path.append(current_node)
    # 判断是否为叶子节点，是则返回当前路径
    if len(current_node.children) == 0:
        return current_path.copy()
    # 遍历所有子节点查找有效路径
    for child in current_node.children:
        res = find_valid_path(child, current_path)
        # 找到第一条有效路径直接返回，无需继续遍历
        if res is not None:
            return res
    # 所有子分支都无效，回溯移除当前节点
    current_path.pop()
    return None

# 调用入口
result = find_valid_path(root_node, [])
# 结果处理：result非空即为找到的完整路径，为空说明不存在符合要求的路径

可选优化 #

如果你需要查找所有符合要求的根到叶全激活路径，只需要去掉找到路径就提前返回的逻辑，把所有命中的路径存入全局结果列表，遍历完整棵树后统一返回即可。由于给定的树本身无环，不需要额外添加访问标记避免重复遍历。

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