java - 如何在将子节点添加到父节点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 - 否则你不知道何时停止在更高级别的递归上迭代
• visitedNode需要是 List<Node> - 否则你会被单个项目的名称所困扰
• 何时 findLoop里面for(...)返回true ，方法返回true立即 - 这可以确保积极的信息不会被忽略

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