无法获得从根节点到点的正确路径

Question

我试图找到从根节点到给定点的路径，但最终得到一个空数组。在输出中，我应该获取从根到给定点的路径 id 字符串列表。请查看以下链接以获取有关问题的详细说明。

问题陈述

我已经尝试了下面的代码来获取字符串 ID。

public static List<String> findPathToNode(Node rootNode, Point toFind) {
// @ToDo Implement this routine
List<String> nodeList = new ArrayList<>();
return getAllNodesForPoint(rootNode, toFind, nodeList);   }
//Recursive function to loop through all nodes of tree and return empty LinkedList   // if point not found or NOT Empty with the path to the point, if point is found
static List<String> getAllNodesForPoint(Node n, Point p, List<String> list) {
list.add(n.getId());
for (Node temp : n.getChildren()) {
if (temp.getChildren().size() > 0) {
if (isContained(temp, p)) {
list.add(temp.getId());
return list;
} else {
getAllNodesForPoint(temp, p, list);
}
} else {
list = new LinkedList<>();
list.add(n.getId());
}
}
list = new ArrayList<>();
return list;   }
static boolean isContained(Node e, Point p){
Point topLeft = new Point(e.getLeft(), e.getTop());
Point topRight = new Point(e.getLeft()+e.getWidth(), e.getTop());
Point bottomLeft = new Point(e.getLeft(), e.getTop()+e.getHeight());
Point bottomRight = new Point(e.getLeft()+e.getWidth(), e.getTop()+e.getHeight());
if(topLeft.getX()<p.getX()
&&p.getX()<topRight.getX()
&&topLeft.getY()<p.getY()
&&bottomLeft.getY()>p.getY()){
return true;
}
else{
return false;
}   }

提前谢谢你!!

Answer 1

下面是可以完成问题语句中所述工作的代码片段：

private static void getPath(Node root, Point p, List<String> result) {
if (root != null) {
result.add(root.getId());
List<Node> childNodes = root.getChildren();
if (childNodes != null && !childNodes.isEmpty()) {
Node child = null;
for (Node node : childNodes) {
if (isLeftBoundCondtionMet(node, p) && isTopBoundCondtionMet(node, p)) {
child = node;
}
}
getPath(child, p, result);
}
}
}
public static Boolean isLeftBoundCondtionMet(Node root, Point p) {
return root.getLeft() < p.getX() && (p.getX() < (root.getLeft() + root.getWidth()));
}
public static Boolean isTopBoundCondtionMet(Node root, Point p) {
return root.getTop() < p.getY() && (p.getY() < (root.getTop() + root.getHeight()));
}

Answer 2

这部分代码片段有错误

for (Node temp : n.getChildren()) {
if (temp.getChildren().size() > 0) {
if (isContained(temp, p)) {
list.add(temp.getId());
return list;
} else {
getAllNodesForPoint(temp, p, list);
}
} else {
list = new LinkedList<>();
list.add(n.getId());
}
}
list = new ArrayList<>();
return list;  

我们可以使用您的问题陈述中给出的示例来解释相同的内容。

例：

{"id": "root" ,
"left": 0 , 
"top": 0 ,
"width": 33 , 
"height": 23 ,
"children": [{
"id": "child-0" ,
"left": 5 , 
“top": 5 ,
"width": 20 ,
"height": 10 ,
"children": []},
{"id": "child-1" ,
"left": 10 ,
"top": 10 ,
"width": 20 ,
"height": 10 ,
"children": []
}
]}

它从root节点开始，在其children数组中有两个子节点child-0和child-1。因此，它将进入这部分代码

for (Node temp : n.getChildren())

现在这个for循环将运行 2 次，因为root节点有两个子节点。

但是数组的每个子children都是空的，因此它将无法进入此代码：

if (temp.getChildren().size() > 0)

相反，它将进入else部分。 但第一个问题到这里结束了。在这里，您每次都初始化一个数组列表并添加此子 Id。 因此，当循环第一次运行时child-1它将通过以下方式创建一个新列表

list = new LinkedList<>();

并向其添加child-1。 下次它将再次运行child-2并重新初始化列表并向其中添加child-2。

因此，在我们列表中的for循环结束时，我们将只有 1 个条目child-2.

但是你得到的是空列表，因为在结束 for 循环后，你再次重新初始化了列表，并且你返回了空列表。这是第二个问题。

list = new ArrayList<>();
return list;

更正后的getAllNodesForPoint代码是

list.add(n.getId());
for (Node temp : n.getChildren()) {
if (temp.getChildren().size() > 0) {
if (isContained(temp, p)) {
list.add(temp.getId());
return list;
} else {
getAllNodesForPoint(temp, p, list);
}
} else {
list.add(temp.getId());
}
}
return list;   }