Hallo.
Die Liste ist folgendermaßen aufgebaut:
Beispiel für die Folge:
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2
Der Wurzelknoten ist die gesamte äußere Liste, das heißt alle Zahlen oben.
Die erste Zahl in einem Knoten gibt die Anzahl der Kindsknoten an. Im oberen Beispiel hat der Wurzelknoten also zwei Kinder. Die zweite Zahl gibt an wieviele Zahlen am Ende des Knotens stehen. Im oberen Beispiel beginnt der Wurzelknoten mit 2 und 3. Das heißt der Wurzelknoten hat 2 Kinder und die letzten drei Zahlen sind 1 1 2.
Das erste Kind vom Wurzelknoten ist 0 3 10 11 12. Dieser Knoten hat 0 Kinder und 3 Zahlen am Ende, die 10 11 und 12.
Das zweite Kind vom Wurzelknoten ist 1 1 0 1 99 2. Dieser Knoten hat 1 Kind und 1 Zahl am Ende.
Das Kind vom zweiten Kind ist 0 1 99. Dieser Knoten hat 0 Kinder und 1 Zahl am Ende (99)
Das ganze möchte ich dann am Ende als Map darstellen. Wobei eine Subliste (ein Knoten) als Schlüssel und alle Kinder dieses Knotens als List<List<Integer>> dargestellt werden sollen.
Folgende Methode funktioniert zwar, aber ich habe einen off-by-one error und keine Ahnung wie ich diesen beheben kann.
Die Methode gibt immer den Index des nächsten Knotens zurück, welcher dann genutzt wird um die Sublisten zu bilden.
Die Ausgabe die ich am Ende erhalte wenn ich die Map durchgehe ist folgende:
Das Problem an der Sache ist, dass ich nicht vorher weiß, wo ein Knoten endet. Deshalb muss ich rekursiv runter bis ich einen Knoten ohne Kinder erwische.
Was ich am Ende haben möchte, sind alle Knoten und Kindsknoten (als adjacency List). Gibt es hier einen einfacheren Ansatz den ich übersehen habe?
Die Liste ist folgendermaßen aufgebaut:
Beispiel für die Folge:
2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2
Der Wurzelknoten ist die gesamte äußere Liste, das heißt alle Zahlen oben.
Die erste Zahl in einem Knoten gibt die Anzahl der Kindsknoten an. Im oberen Beispiel hat der Wurzelknoten also zwei Kinder. Die zweite Zahl gibt an wieviele Zahlen am Ende des Knotens stehen. Im oberen Beispiel beginnt der Wurzelknoten mit 2 und 3. Das heißt der Wurzelknoten hat 2 Kinder und die letzten drei Zahlen sind 1 1 2.
Das erste Kind vom Wurzelknoten ist 0 3 10 11 12. Dieser Knoten hat 0 Kinder und 3 Zahlen am Ende, die 10 11 und 12.
Das zweite Kind vom Wurzelknoten ist 1 1 0 1 99 2. Dieser Knoten hat 1 Kind und 1 Zahl am Ende.
Das Kind vom zweiten Kind ist 0 1 99. Dieser Knoten hat 0 Kinder und 1 Zahl am Ende (99)
Das ganze möchte ich dann am Ende als Map darstellen. Wobei eine Subliste (ein Knoten) als Schlüssel und alle Kinder dieses Knotens als List<List<Integer>> dargestellt werden sollen.
Folgende Methode funktioniert zwar, aber ich habe einen off-by-one error und keine Ahnung wie ich diesen beheben kann.
Die Methode gibt immer den Index des nächsten Knotens zurück, welcher dann genutzt wird um die Sublisten zu bilden.
Java:
private static int formTree(List<Integer> nums, Map<List<Integer>, List<List<Integer>>> tree, int current)
{
int childCount = nums.get(current);
int metaDataAmount = nums.get(current + 1);
if(childCount == 0)
{
int p = current + 2;
for(int i = 0; i < metaDataAmount; i++)
{
p++;
}
return p;
}
else
{
//create parent
List<Integer> parent = new ArrayList<Integer>();
int p = current + 2;
for(int i = 0; i < childCount; i++)
{
p = formTree(nums, tree, p);
}
for(int i = current; i < p + metaDataAmount + 1; i++)
{
parent.add(nums.get(i));
}
if(!tree.containsKey(parent))
{
tree.put(parent, new ArrayList<List<Integer>>());
}
//create all children
p = current + 2;
for(int i = 0; i < childCount; i++)
{
int firstIndexChild = p;
p = formTree(nums, tree, p);
List<Integer> child = new ArrayList<>();
for(int j = firstIndexChild; j < p; j++)
{
child.add(nums.get(j));
}
if(!tree.get(parent).contains(child))
{
tree.get(parent).add(child);
}
}
return p;
}
}Die Ausgabe die ich am Ende erhalte wenn ich die Map durchgehe ist folgende:
Java:
Parent: [2, 3, 0, 3, 10, 11, 12, 1, 1, 0, 1, 99, 2, 1, 1, 2] //richtig
Children:
[0, 3, 10, 11, 12] //richtig
[1, 1, 0, 1, 99] //sollte 1 1 0 1 99 2 sein
Parent: [1, 1, 0, 1, 99, 2, 1] //sollte 1 1 0 1 99 2 sein
Children:
[0, 1, 99] //richtigDas Problem an der Sache ist, dass ich nicht vorher weiß, wo ein Knoten endet. Deshalb muss ich rekursiv runter bis ich einen Knoten ohne Kinder erwische.
Was ich am Ende haben möchte, sind alle Knoten und Kindsknoten (als adjacency List). Gibt es hier einen einfacheren Ansatz den ich übersehen habe?
