stampa nodi specifico in un ogni livello calcolato da una data funzione

Question

In un'intervista, mi è stata data una funzione:

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... 

Per ogni livello n di un dato N-Array devo stampare il f (n) del nodo ad ogni livello Per esempio:

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 

Se il number of nodes(say nl) a qualsiasi livello n è less than f(n), quindi devono stampare node number nl%f(n) counting from the left.

Ho eseguito un ordine trasversale di livello base utilizzando una coda, ma ero bloccato su come contare i nodi ad ogni livello e gestire la condizione quando il numero di nodi a qualsiasi livello n è less than f(n).

Suggerisci un modo per continuare per la parte rimanente del problema.

Answer 1

aggiunte soluzione here

ho usato coda per leggere tutti i nodi ad un livello particolare, prima di leggere i nodi verificando se dato livello (n) sia uguale al livello attuale, allora il controllo del formato della coda è maggiore di f (n) quindi basta leggere f (n) nodi dalla coda e contrassegnarlo come cancellato altrimenti eseguire l'operazione mod ed eliminare il nodo nl% f (n).

Answer 2

È necessario eseguire il livellamento dell'ordine di livello .

Nel seguente codice sto assumendo due metodi:

• Uno è getFn(int level) che prende in un int e restituisce il valore f (n);
• Un altro è printNth(int i, Node n) che accetta un numero int e un nodo e stampa splendidamente che "{n} è quello desiderato per il livello {i}".

Il codice è semplice da implementare ora. I commenti lo spiegano come una storia ...

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