Print Spezifische Knoten bei jeder einer Ebene durch eine gegebene Funktion

Question

In einem Interview berechnet wurde ich eine Funktion gegeben:

f(n)= square(f(n-1)) - square(f(n-2)); for n>2 
f(1) = 1; 
f(2) = 2; 
Here n is the level of an n-array tree. f(n)=1,2,3,5,16... 

Für jede Ebene n eines gegebenen N-Array Ich habe die f (n) Knoten drucken auf jeder Ebene. Zum Beispiel:

At level 1 print node number 1 (i.e. root) 
At level 2 print node number 2 (from left) 
At level 3 print node number 3 (from left) 
At level 4 print node number 5... and so on 

Wenn die number of nodes(say nl) auf jeder Ebene nless than f(n) ist, dann haben node number nl%f(n) counting from the left zu drucken.

Ich habe eine grundlegende Ebene Reihenfolge Traversal mit einer Warteschlange, aber ich war fest, wie Knoten auf jeder Ebene zählen und behandeln die Bedingung, wenn die Anzahl der Knoten auf jeder Ebene n ist.

Schlagen Sie einen Weg vor, um für den verbleibenden Teil des Problems fortzufahren.

Answer 1

zugegebene Lösung here

I Warteschlange verwendet haben alle Knoten auf einer bestimmten Ebene zu lesen, bevor der Knoten zu lesen, wenn gegebenen Pegel überprüft (n) zur Strompegel gleich ist dann der Warteschlange Prüfen Größe größer als f (n) dann lese gerade f (n) Knoten aus der Warteschlange und markiere sie als gelöscht, ansonsten führe die Mod-Operation durch und lösche den Knoten nl% f (n).

Answer 2

Sie müssen Level Order Traversal durchführen.

In dem folgenden Code Ich gehe davon aus zwei Methoden:

• Eins ist getFn(int level), die in einem int nimmt und die f (n) Wert ist;
• Eine andere ist printNth(int i, Node n), die ein int und Node übernimmt und schön druckt, dass "{n} das gewünschte für level {i}" ist.

Der Code ist jetzt einfach zu implementieren. Kommentare erklären es wie eine Geschichte ...

public void printNth throws IllegalArgumentException (Node root) { 

    if (root == null) throw new IllegalArgumentException("Null root provided"); 

    //Beginning at level 1 - adding the root. Assumed that levels start from 1 
    LinkedList<Node> parent = new LinkedList<>(); 
    parent.add(root) 
    int level = 1; 

    printNth(getFn(level), root); 

    //Now beginning from the first set of parents, i.e. the root itself, 
    //we dump all the children from left to right in another list. 
    while (parent.size() > 0) { //Last level will have no children. Loop will break there. 

     //Starting with a list to store the children 
     LinkedList<Node> children = new LinkedList<>(); 

     //For each parent node add both children, left to right 
     for (Node n: parent) { 
      if (n.left != null) children.add(n.left); 
      if (n.right != null) children.add(n.right); 
     } 

     //Now get the value of f(n) for this level 
     level++; 
     int f_n = getFn(level); 

     //Now, if there are not sufficient elements in the list, print the list size 
     //because children.size()%f(n) will be children.size() only! 
     if (children.size() < f_n) System.out.println(children.size()); 
     else printNth(level, children.get(f_n - 1)); //f_n - 1 because index starts from 0 

     //Finally, the children list of this level will serve as the new parent list 
     //for the level below. 
     parent = children; 
    } 
}