Не получается правильный путь от узла root к точке

Question

Я пытаюсь найти путь от узла root к заданной точке, но в итоге получаю пустой массив. На выходе я должен получить список строк идентификаторов пути от root до заданной точки. Пожалуйста, проверьте ниже ссылку для подробного описания проблемы.

Постановка проблемы

Я пробовал ниже код, чтобы получить идентификаторы строки.

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" ,
"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. Из-за этого он будет go в этой части кода

for (Node temp : n.getChildren())

Теперь этот for l oop будет выполняться 2 раза, поскольку есть два дочерних элемента узла root.

Но каждый дочерний массив children пуст, поэтому он не сможет набрать go в этом коде кода:

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

, вместо этого он будет go в части else. Но первый выпуск здесь. Здесь вы каждый раз инициализируете список массивов и добавляете этот дочерний идентификатор. Итак, когда l oop запускается в первый раз для child-1, он создаст новый список с этим

list = new LinkedList<>();

и добавит к нему child-1. и в следующий раз он снова запустится для child-2, переинициализирует список и добавит к нему child-2.

Итак, в конце for l oop в нашем списке у нас будет только 1 запись child-2.

Но в результате вы получаете пустой список, потому что после окончания для l oop вы снова повторно инициализировали список и возвращаете пустой список. Это вторая проблема .

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;   }

Answer 2

Ниже приведен фрагмент кода, который будет выполнять работу, указанную в описании проблемы:

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()));
}