drukowania określonych węzłów w w każdym etapie oblicza się za pomocą danej funkcji

Question

w wywiadzie, dano funkcję:

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

Dla każdego poziomu n danego N-Array muszę drukowania f (n) węzła na każdym poziomie. Na przykład:

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 

Jeśli number of nodes(say nl) na każdym poziomie n jest less than f(n), następnie trzeba wydrukować node number nl%f(n) counting from the left.

Wykonałem podstawowe przejście na poziomie rzędu przy użyciu kolejki, ale utknąłem na tym, jak liczyć węzły na każdym poziomie i obsługiwać stan, gdy liczba węzłów na dowolnym poziomie n jest less than f(n).

Zaproponuj sposób postępowania w przypadku pozostałej części problemu.

Answer 1

dodano roztwór here

I stosuje kolejkę odczytywać wszystkie węzły na określonym poziomie, przed odczytaniem węzły sprawdzenie, czy dany poziom (n) jest równy aktualnej poziomu, sprawdzenie wielkości kolejki jest większa niż F (n) po prostu odczytaj f (n) węzły z kolejki i oznacz je jako usunięte, w przeciwnym razie wykonaj operację mod i usuń węzeł nl% f (n).

Answer 2

Musisz wykonać Traversal poziomu zamówienia.

W kodzie poniżej ja przyjmując dwa sposoby:

• jeden oznacza getFn(int level) która odbywa się w Int i zwraca wartość f (n);
• Innym jest printNth(int i, Node n), który przyjmuje int i węzeł i pięknie drukuje, że "{n} jest pożądany dla poziomu {i}".

Kod jest prosty do wdrożenia teraz. Komentarze wyjaśniają to jako historię ...

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