我有一个表示为Set< Integer> []的树
以下Set< Integer> []：
[ { 1 },{ 2,3 },{ 4 },{ 5,6,7 } ]
代表以下树：
1
/ \
/ \
/ \
2 3
| |
4 4
/|\ /|\
5 6 7 5 6 7
因此树中的每个级别都被编码为Set.树中特定级别的所有子集都是相同的.第一组中可以有多个整数.
我想从Set< Integer> []中获取从root到leaves的所有路径的列表：
[ [ 1,2,4,5 ],[ 1,6 ],7 ],3,7 ] ]
最佳答案
在树中搜索的密钥通常是实现良好的Ajacency函数,该函数为特定节点提供相邻节点.
原文链接：https://www.f2er.com/java/437868.html对于此树,邻接函数将希望找到节点所在的级别,然后将下一级别的节点作为邻接返回.它看起来像这样：
/**
* This returns the adjacent nodes to an integer node in the tree
* @param node
* @return a set of adjacent nodes,and null otherwise
*/
public Set假设我们已经将树定义为类中的字段.
在我们运行搜索之前,我们希望适当地设置根目录并对路径做一些预备工作.因此,我们执行以下操作：
/**
* initializes our search,sets the root and adds it to the path
*/
public void initialize() {
root = -1;
for (Integer node : tree.get(0)) {
root = node;
}
currentPath.add(root);
}
假设currentPath和root已经定义为字段.
然后,当我们遍历树时,我们在树上运行DFS搜索,将每个节点附加到当前路径,并将该路径添加到我们的设置路径,并在到达deadend(叶子)时重置它：
/**
* runs a DFS on the tree to retrieve all paths
* @param tree
*/
public void runDFS(Integer node) {
if (getAdjacentsToNode(node) != null) {
for (Integer adjNode : getAdjacentsToNode(node)) {
currentPath.add(adjNode);
runDFS(adjNode);
}
currentPath.remove(currentPath.size() -1);
} else {
paths.add(currentPath.toArray(new Integer[0]));
currentPath.remove(currentPath.size() -1);
}
}
因此,整个班级看起来像这样：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class DFS {
private List为了测试它,我们试试这个：
public static void main(String[] args) {
ArrayList我们得到以下输出：
[1,5]
[1,6]
[1,7]
[1,7]
