我有一棵树 . 此树中的所有节点都具有一些true / false值，一个元素和父/子指针 . 此树中的一个元素将true / false值设置为true . 我想找到从根到这个唯一节点的路径（元素序列） . 所以，如果我的树看起来像这样：
A
/ \
B C
/ \
D E
/ \
F G
/ \
H I
并且特殊节点是H，我的算法将返回字符串“ACEGH” . 我已经使用DFS实现了这一点 . 但是，我当前的算法是从不正确的路径添加节点的元素 . 所以我现在的算法将返回：“ABDCEFGHI” .
private String dfs(Node node, String path) {
if(node.special){
return key;
}
for(Node n: node.children){
if(n != null){
path = path + n.element;
dfs(n, path);
}
}
return null;
}
1 回答
如果
dfs返回null（解释为表示尚未找到解决方案路径），则需要从路径中删除n.element. 一旦dfs返回非空，您还应该停止检查子项 .为此，
dfs应该在找到路径后返回非null，无论它处于什么级别 .