1

我有一个带有子节点列表的节点模型，如下所示：

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

有人可以在这里给我一些提示吗？太感谢了！

4

1 回答 1

0

由于您已经非常接近想要获得的结果，这里有几个关于如何完成任务的提示：

  • findLoop需要返回boolean- 否则您将不知道何时停止以更高级别的递归进行迭代
  • visitedNode必须是List<Node>- 否则你会被一个项目的名字困住
  • 当findLoop内部for(...)返回时true，方法true立即返回- 这确保不会忽略正面的

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

于 2019-03-13T15:57:32.167 回答