DFS：使用深度优先搜索（java）查找节点路径

Question

我有一棵树。此树中的所有节点都有一些真/假值、一个元素和父/子指针。此树中的一个元素的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;
}

Answer 1

如果dfs返回null，则需要从路径中删除n.element（将此解释为未找到解决方案路径）。一旦dfs返回非空，您也应该停止检查子元素。

要使其正常工作，dfs在找到路径后应返回非null，而不管它处于什么级别。