在将子节点添加到父节点Java之前，如何检测循环

Question

我有一个节点模型，如下所示：

：

class Node {
    private String name;
    private List<Node> childNodes;
    public Node(String name, List<Node> childNodes) {
        this.name = name;
        this.childNodes = childNodes;
    }
    public Node(String name) {
        this(name, new ArrayList<>());
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public List<Node> getChildNodes() {
        return childNodes;
    }
    public void setChildNodes(List<Node> childNodes) {
        this.childNodes = childNodes;
    }
    public void addChildNodes(Node childNode) {
        this.getChildNodes().add(childNode);
    }
}

我要做的是检查在父节点添加子节点时是否产生循环。循环在这里意味着子节点的名称与直接或间接父母相同。当检测到循环时，我还想打印出哪些节点在此循环中满足。我做的是：

    private static void findLoop(Node currentNode, String orginalNodeName, String visitedNode) {
        if (currentNode != null && !currentNode.getChildNodes().isEmpty()) {
            for (Node childNode : currentNode.getChildNodes()) {
                visitedNode = visitedNode + "->" + childNode.getName();
                if (childNode.getName().equals(orginalNodeName)) {
                    System.out.println("Loop is detected: " + visitedNode);
                }
                findLoop(childNode, orginalNodeName, visitedNode);
            }
        }
    }

我的想法是通过所有子节点循环，从我要检查的节点开始，并比较当前节点是否具有与原始启动节点相同的名称，如果是，则检测到一个循环。

它有效，但我无法正确打印循环的内容，因为它循环穿过父节点的所有可能的子节点，例如：

            parentNode
    node1                node2
  childNode1           childNode2
                parentNode   childChildNode2

它打印：parentNode->node1->node2->childNode2->parentNode，我想打印的是：parentNode->node2->childNode2->parentNode

有人可以在这里提示我吗？非常感谢！

Answer 1

，由于您非常接近要获得的结果，因此有几个提示您如何完成任务：

• findLoop需要返回boolean - 否则您将不知道何时停止在递归的higer级别进行迭代
• visitedNode需要是List<Node> - 否则您会被单个项目的名称
粘住
• 当for(...)中的findLoop返回true时，方法返回true立即 - 这确保阳性不会被忽略

最后，不要忘记findLoop需要从子节点开始，而不是为父节点循环，而不是相反。