没有从根节点到点的正确路径

Question

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

Problem Statement

我已经尝试过下面的代码来获取字符串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

您的这段代码片段中有错误

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”，“左”：0，“顶部”：0，“宽度”：33，“身高”：23，“儿童”：[{“ id”：“ child-0”，“左”：5，“前5 ，“宽度”：20，“身高”：10，“儿童”：[]}，{“ id”：“ child-1”，“左”：10，“前10名 ，“宽度”：20，“身高”：10，“儿童”：[]}]}

从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(n.getId());
      }
    }
    return list;   }