递归算法算路径Java实现
时间: 2023-02-27 21:47:04 浏览: 49
好的,下面是一个用 Java 实现递归算法求路径的例子:
```
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> path = findPath(new Node("A"));
System.out.println(path); // 输出:[A, B, C, D]
}
public static List<String> findPath(Node node) {
if (node == null) {
return new ArrayList<>();
}
if (node.isEndNode()) {
List<String> path = new ArrayList<>();
path.add(node.getName());
return path;
}
List<String> path = findPath(node.getNextNode());
path.add(0, node.getName());
return path;
}
static class Node {
private final String name;
private final Node next;
public Node(String name) {
this.name = name;
this.next = null;
}
public Node(String name, Node next) {
this.name = name;
this.next = next;
}
public boolean isEndNode() {
return next == null;
}
public Node getNextNode() {
return next;
}
public String getName() {
return name;
}
}
}
```
在上面的代码中,我们使用了一个节点类 `Node` 来表示路径上的每一个点,并使用递归的方法求出从起点到终点的路径。
在 `findPath` 方法中,我们首先判断当前节点是否为空,如果是,直接返回一个空的路径列表。如果当前节点是终点,则返回一个只包含终点名称的路径列表。否则,我们递归调用 `findPath` 方法,求出从下一个节点到终点的路径,然后将当前节点的名称插入到路径的开头,最后返回