题目重点：电面只给边表示树、标记若干失效节点、输出不含失效节点的 preorder；本文把失效即跳过整棵子树作为训练契约并验证。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版有一棵有向根树，边 (parent,child) 的给定顺序决定兄弟顺序；根由只出现在 parent 或未出现在 child 集合中的唯一节点确定。
- 失效节点相当于剪掉整个子树，其后代也不可达；若真实题要求只跳过失效节点但把子孙提到上一层，遍历语义和实现都需更换。
- 空边列表返回空序列，因为未给孤立根的 node 列表；重复父节点、环或断开的图报错。
解题路线
- 建 parent→children 邻接表及 child→parent 映射，核唯一根与每节点最多一个 parent。
- 先忽略失效标记验证所有节点确实构成一棵树，防止纯环藏在另一个连通块中；再从根做显式栈先序遍历。
- 每访问一个节点，若失效直接跳过该节点及整棵后代；否则输出当前节点，并把 children 逆序压栈，使弹栈次序等于输入边顺序。
- 用独立递归 DFS 基线在随机树、随机失效标记下做 10,000 组对照，覆盖失效根、兄弟顺序与整支剪除。
手动走一遍
边 A→B、A→C、B→D、B→E，若 B 失效，训练版输出 [A,C]；D/E 虽未单独标记失效，但位于被剪子树。若题意为‘只过滤失效节点’，则会得到 [A,D,E,C]，需要先问清。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training rule: disabled nodes remove their full descendant subtree."""
def active_preorder(edges: list[tuple[str, str]], disabled: set[str]) -> list[str]:
children = {}
parent = {}
people = set()
for upper, lower in edges:
if upper == lower or lower in parent:
raise ValueError("not a rooted tree")
parent[lower] = upper
children.setdefault(upper, []).append(lower)
people.update((upper, lower))
if not people:
return []
roots = people - parent.keys()
if len(roots) != 1 or len(edges) != len(people) - 1:
raise ValueError("not a rooted tree")
root = next(iter(roots))
reachable = set()
pending = [root]
while pending:
node = pending.pop()
if node in reachable:
raise ValueError("cycle")
reachable.add(node)
pending.extend(children.get(node, []))
if reachable != people:
raise ValueError("disconnected tree")
output = []
seen = set()
stack = [root]
while stack:
node = stack.pop()
if node in seen:
raise ValueError("cycle")
seen.add(node)
if node in disabled:
continue
output.append(node)
stack.extend(reversed(children.get(node, [])))
return output
复杂度
N 节点、E=N−1 边，构图、合法性检查和遍历 O(N+E) 时间、O(N+E) 空间。先验完整树验证即使根已失效也扫描全图，是为了明确拒绝坏输入。
易错点与追问
容易失分的边界
- 未确认失效节点是否屏蔽后代，就把一种语义说成原题唯一要求。
- 栈遍历按正序压入孩子，输出兄弟顺序被反转。
- 有多个根或带环时任意选一个根并返回部分序列。
- 树根失效后仍输出其子孙，和剪子树约定不符。
- 只有边表时凭空补出孤立节点。
继续深挖
- 若要求过滤节点但保留后代，遍历如何改？
- 失效标记频繁更新且每次查询先序结果，如何缓存与失效？
- 若输入是无向 edges，怎样确定根与孩子方向？
