Cześć,
Ostatnio znajomy miał takie zadanie na rekrutacji:
Jest klasa
class TestTree {
int weight;
String name;
List<TestTree> children;
}
Mając takie drzewo, policzyć ile Nodów ma weight > 3. Przy użyciu rekurencji szybko poleci stackoverflow. Osoba rekrutująca powiedziała, że można to rozwiązać używając pointerów. Mowiąc szczerze próbowałem to rozwiązać i jedyne na co wpadłem to takie coś:
Do klasy TestTree musimy dodać dwa pola: TestTree parent raz int indexToProcess. Wtedy taki kod zadziała:
static void traversall(TestTree root) {
if (root == null)
return;
TestTree current = root;
while (root.getChildren().size() != root.indexToProcess) {
if(current.getChildren() != null) {
if(current.getChildren().size() == current.indexToProcess) {
System.out.println("Process " + current.name);
current.parent.indexToProcess++;
current = current.parent;
continue;
}
TestTree temp = current;
current = current.getChildren().get(current.indexToProcess);
current.parent = temp;
} else {
//jestem na samym dole
System.out.println("Process " + current.name);
current.parent.indexToProcess++;
current = current.parent;
}
}
System.out.println("Process " + root.name);
}
Natomiast mam wątpliwości czy to jest poprawne? Próbowałem rozwiązać to bez dodawania tych zmiennych, ale przy dużym drzewie jak zejdę na sam dół to nie będę w stanie wrócić do góry. Ktoś ma może jakiś inny pomysł?