hacer - programacion java contador

Intentando imprimir la vista superior de un árbol usando dos sentencias if

Question

Planteamiento del problema

Le dan un puntero a la raíz de un árbol binario. Imprime la vista superior del árbol binario. Solo tienes que completar la función.

Mi código:

void top_view(Node root)
 {  
       Node r = root;

       if(r.left!=null){
          top_view(r.left);
          System.out.print(r.data + " ");
        }
       if(r.right!=null){
          System.out.print(r.data + " ");
          top_view(r.right);
        }
}

Las dos sentencias if se ejecutan cada vez que se llama a la función, pero solo necesito ejecutar una de ellas. Probé el interruptor, pero está dando error de expresión constante. Ya he encontrado una solución diferente para este problema.

Entonces solo quiero saber si podemos hacer solo uno si se ejecuta a la vez, es decir, ¿hay alguna manera de arreglar mi código sin cambiar el enfoque?

Enlace del problema: https://www.hackerrank.com/challenges/tree-top-view

Answer 1

Una forma recursiva simple de hacerlo:

void top_view(Node root)
{
    print_top_view(root.left, "left");
    System.out.print(root.data  + " ");
    print_top_view(root.right, "right");
}

void print_top_view(Node root, String side) {
    if(side.equals("left")) {
        if(root.left != null) {
            print_top_view(root.left, "left"); 
        }
       System.out.print(root.data + " ");
    } else if(side.equals("right")) {
        System.out.print(root.data + " ");
        if(root.right != null) {
          print_top_view(root.right, "right");  
        } 
    }
}

Answer 2

Su enfoque no funcionará porque, cuando llame right subárbol left o right , simplemente lo mantendrá. El problema con este enfoque es que simplemente te indica por qué lado del árbol se llama primero.

Puede ser que puedas resolverlo usando la pila y la cola como alguien más dijo, pero creo que el siguiente es un enfoque más simple e intuitivo:

(VEA EL CÓDIGO AL FINAL, ES MUY SIMPLE)

El enfoque para resolver esto es mantener la horizontal distance desde la raíz e imprimir el primer nodo para cada horizontal distance diferente.

¿Qué es la distancia horizontal?

Solo estoy tomando la imagen que ha agregado.

Horizontal distance para un node particular se define como el número de origen desde la raíz. Si ve no. De bordes que se convertirán en distancia vertical.

Para facilitar las cosas para todos los nodos en el lado izquierdo de la raíz, comience con -ve distancia horizontal y distancia positiva del lado derecho.

¿Cómo se calcula la distancia horizontal?

Si va bien, add 1 , si va hacia la izquierda, agregue -1 .

asi que

    horizontal distance of 3 = 0

    horizontal distance of 5 = -1
    horizontal distance of 1 = -2
    horizontal distance of 9 = -1
    horizontal distance of 4 = 0

    horizontal distance of 2 =  1
    horizontal distance of 6 =  0
    horizontal distance of 7 =  2
    horizontal distance of 8 =  0

Los nodos 3,4,6,8 tienen la misma distancia horizontal de 0 ¿qué significa?

Eso significa que cuando se ve desde arriba todos estos nodos están en una línea verticalmente uno encima.

Si están en una línea vertical, ¿cuál ves?

El que se puede alcanzar primero desde la raíz.

¿Cómo puede encontrar cuál se puede alcanzar primero?

como es habitual BFS

¿Cómo esto imprime la solución para su ejemplo?

Hay cinco valores diferentes de distancia horizontal {-1, -2,0,1,2}

hor dist        Nodes

   0      - {3,6,8} // 3 comes first in BFS so print 3
  -1      - {5,9}   // 5 comes first in BFS so print 5
  -2      - {1}     // just print 1
   1      - {2}     // just print 2
   2      - {7}     // just print 7

Entonces imprimirá {3,5,1,2,7}

HashSet<Integer> set = new HashSet<>();
Queue<QueueItem> queue = new LinkedList<>();
queue.add(new QueueItem(root, 0)); // Horizontal distance of root is 0

while (!queue.isEmpty())
{
    QueueItem temp = queue.poll();
    int hd = temp.hd;
    TreeNode n = temp.node;

    // If this is the first node at its horizontal distance,
    // then this node is in top view
    if (!set.contains(hd))
    {
        set.add(hd);
        System.out.print(n.key + " ");
    }

    if (n.left != null)
        queue.add(new QueueItem(n.left, hd-1));
    if (n.right != null)
        queue.add(new QueueItem(n.right, hd+1));
}

Answer 3

La solución es bastante fácil si imprime el lado izquierdo por recursión y el lado derecho con un ciclo while simple.

 void for_left(node *root)
{
    if(!root->left)
        {
        cout<<root->data<<" ";
        return;
    }
    for_left(root->left);
    cout<<root->data<<" ";
    return;

}

void top_view(node * root)
{
    for_left(root->left);
    cout<<root->data<<" ";
    while(root->right)
        {
        cout<<(root->right)->data<<" ";
        root=root->right;
    }


}

Answer 4

Mi implementación de Java está conectada. El lado izquierdo del árbol es más interesante si se resuelve recursivamente, pero invertir la cuerda (mi camino a continuación) fue más fácil y solo requirió el uso de un método.

public void top_view(Node root){

    String output = "";

    Node left = root.left;
    Node right = root.right;

    String leftOutput = "";
    while(left != null){
        leftOutput += left.data + " ";
        left = left.left;
    }

    String left = "";
    for(int i = leftOutput.length - 1; i >= 0; i--){
        left += leftOutput.substring(i, i+1);
    }

    output += left;

    output += " " + root.data + " ";

    while(right != null){
        output += right.data + " ";
        right = right.right;
    }

    output = output.substring(1, output.length());
    System.out.println(output);
}

Answer 5

void top_view(Node root)    
{    
    if(root.left!=null) top_view(root.left);   

    if(root.left!=null || root.right!=null)
         System.out.print(root.data + " ");

    if(root.right!=null) top_view(root.right);        
}

Answer 6

Un enfoque más simple en C ++

`// printing top view of the tree
void left_array(node *p)
{
    if(p==NULL)
    return;
    else
    {
        left_array(p->left);
        cout<<p->data<<" ";
    }
}
void right_array(node *p)
{
    if(p==NULL)
    return;
    else
    {
        cout<<p->data<<" ";
        right_array(p->right);
    }

}
void top_view(node * root)
{   int i=0;
node *t1=root;
node *t2=root;
    left_array(t2);
    right_array(t1->right);

}`

Answer 7

Una solución recursiva muy simple que se ocupa de las ramas largas del nodo hijo. Esto se resuelve utilizando el concepto de distancia horizontal.

public void printTopView(BNode root) {
        Map<Integer, Integer> data = new TreeMap<Integer, Integer>();
        printTopViewRecursive(data, root, 0);
        for(int key : data.keySet()) {
            System.out.print(data.get(key) +" ");
        }
    }


    private void printTopViewRecursive(Map<Integer, Integer> hDMap, BNode root, int hD) {
        if(root == null)
            return;
        if(!hDMap.containsKey(hD)) {
            hDMap.put(hD, root.data);
        }
        printTopViewRecursive(hDMap, root.left,hD - 1);
        printTopViewRecursive(hDMap, root.right, hD + 1);
    }

Answer 8

Este problema se puede resolver muy fácilmente utilizando:

Pila : para imprimir la raíz y el subárbol izquierdo.

Cola : para imprimir el subárbol derecho.

Tu función debería ser así:

 void topview(Node root)
 {
     if(root==null)
      return;
     Stack<Integer> s=new Stack<Integer>();
     s.push(root.data);
     Node root2=root;
     while(root.left!=null)
     {
      s.push(root.left.data);
      root=root.left;
     }
     while(s.size()!=0)
      System.out.print(s.pop()+" ");

     Queue<Integer> q=new LinkedList<Integer>(); 
     q.add(root2.right.data);
     root2=root2.right;     
     while(root2.right!=null)
     {
      q.add(root2.right.data);
      root2=root2.right;
     }
     while(q.size()!=0)
      System.out.print(q.poll()+" ");
 }

Answer 9

Este realmente funciona. No necesita una cola, pero usa una pila para retroceder desde el lado izquierdo, ya que no tenemos referencia al padre.

void top_view(Node root)
{
    Stack<Node> p = new Stack<Node>();
    Node current = root;
    while (current != null) 
    {
        p.push(current);
        current = current.left;
    }

    while (p.peek() != root) 
    {
        System.out.print(p.pop().data + " ");
    }

    current = root;
    while (current != null) 
    {
        System.out.print(current.data + " ");
        current = current.right;
    }
}

Answer 10

en java recursivish solution. convertido desde código c ++

void top_view(Node root)
{
    left_array(root);
    right_array(root.right);
}

void left_array(Node p)
{
    if(p==null)
        return;
    else
    {
        left_array(p.left);
        System.out.printf("%d ",p.data);
    }
}
void right_array(Node p)
{
    if(p==null)
        return;
    else
    {
        System.out.printf("%d ",p.data);
        right_array(p.right);
    }
}

Answer 11

void top_view(Node root)
 {
    Node left = root;
    Node right = root;
    print_left(root.left);
    System.out.print(root.data + " ");
    print_right(root.right) ;
 }

void print_left(Node start)
 {
    if(start != null)
     {
       print_left(start.left);
       System.out.print(start.data + " "); 
     } 
 }

void print_right(Node start)
 {
    if(start != null)
    {
       System.out.print(start.data + " ");    
       print_right(start.right);
    }     
  } 

Answer 12

if(root){
if(root->left !=NULL || root->right !=NULL){
    if(root->left)
        top_view(root->left);

     cout<<root->data<<" ";

     if(root->right)
        top_view(root->right);

}}

Answer 13

Este es el código para la vista superior de un árbol binario en c ++ ..

void topview (nodo * raíz, cola y Q)

{

if(!root)
    return;
map<int,int> TV;
Q.push(root);
TV[root->data]=0;
map<int,int>:: iterator it;
int min=INT_MAX,max=INT_MIN;
while(!Q.empty())
{
    node* temp =Q.front();
    Q.pop();
    int l=0;

    for(it=TV.begin();it!=TV.end();it++)
    {
        if(it->first==temp->data)
        {
            l=it->second;
           break;
        }

    }
    if(l<min) 
        {min=l;}
    if(l>max) 
        max=l;
    if(temp->left)
    {
        Q.push(temp->left);
        TV[temp->left->data] = l-1;
    }
    if(temp->right)
    {
        Q.push(temp->right);
        TV[temp->right->data] = l+1;
    }
}
cout<<max<<min<<endl;
for(int  i =min;i<=max;i++)
{
    for(it=TV.begin();it!=TV.end();it++)
    {
        if(it->second==i)
        {
            cout<<it->first;
            break;
        }
    }
}

}

void topview_aux (nodo * raíz)

{

queue<node*> Q;

topview(root,Q);

}

Answer 14

La solución recursiva más simple

void top_view(Node root)
{
 // For left side of the tree
    top_view_left(root);
 // For Right side of the tree
    top_view_right(root.right);
}

void top_view_left(Node root){
     if(root != null)
  {     
     // Postorder
     top_view_left(root.left);
     System.out.print(root.data + " ");
  }  
}

void top_view_right(Node root){
    if(root != null)
  {
        //  Preorder
      System.out.print(root.data + " ");
      top_view_right(root.right);
  }  
}

Answer 15

Un enfoque bastante similar al mencionado en @Karthik, pero al mantener el orden, es posponer la impresión hasta el final y mantener los nodos de vista superior ordenados en cola de doble final.

• Garantizamos el orden usando BFS
• Cada ronda verificamos si la distancia horizontal del nodo actual es mayor que la distancia máxima alcanzada en las rondas anteriores (distancia negativa para los nodos izquierdos).
• Se agregaron nuevos nodos de vista superior con -ve distancia (posición izquierda) al extremo izquierdo del deque, mientras que los nodos derechos con + ve distancia se agregaron al extremo derecho.

Solución de muestra en Java

import java.util.*;

class Node {
  int data;
  Node left;
  Node right;

  public Node(int data) {
    this.data = data;
  }
}

enum Position {
  ROOT,
  RIGHT,
  LEFT
}

class NodePositionDetails {
  Node node;
  // Node position in the tree
  Position pos;
  // horizontal distance from the root (-ve for left nodes)
  int hd;

  public NodePositionDetails(Node node, Position pos, int hd) {
    this.node = node;
    this.pos = pos;
    this.hd = hd;
  }
}

public class TreeTopView {
  public void topView(Node root) {
    // max horizontal distance reached in the right direction uptill the current round
    int reachedRightHD = 0;
    // max horizontal distance reached in the left direction uptill the current round
    int reachedLeftHD = 0;

    if (root == null)
      return;

    // queue for saving nodes for BFS
    Queue < NodePositionDetails > nodes = new LinkedList < > ();

    // Double ended queue to save the top view nodes in order
    Deque < Integer > topViewElements = new ArrayDeque < Integer > ();

    // adding root node to BFS queue 
    NodePositionDetails rootNode = new NodePositionDetails(root, Position.ROOT, 0);
    nodes.add(rootNode);

    while (!nodes.isEmpty()) {
      NodePositionDetails node = nodes.remove();

      // in the first round, Root node is added, later rounds left and right nodes handled in order depending on BFS. if the current horizontal distance is larger than the last largest horizontal distance (saved in reachedLeftHD and reachedRightHD)
      if (node.pos.equals(Position.LEFT) && node.hd == reachedLeftHD - 1) {
        topViewElements.addFirst(node.node.data);
        reachedLeftHD -= 1;
      } else if (node.pos.equals(Position.RIGHT) && node.hd == reachedRightHD + 1) {
        topViewElements.addLast(node.node.data);
        reachedRightHD += 1;
      } else if (node.pos.equals(Position.ROOT)) { // reachedLeftHD == 0 && reachedRightHD ==0
        topViewElements.addFirst(node.node.data);
      }

      // Normal BFS, adding left and right nodes to the queue
      if (node.node.left != null) {
        nodes.add(new NodePositionDetails(node.node.left, Position.LEFT, node.hd - 1));
      }
      if (node.node.right != null) {
        nodes.add(new NodePositionDetails(node.node.right, Position.RIGHT, node.hd + 1));
      }
    }

    // print top elements view
    for (Integer x: topViewElements) {
      System.out.print(x + " ");
    }
  }
}

Y para probar:

  public static void main(String[] args) throws java.lang.Exception {
    /**
       Test Case 1 & 2
        1
       /  /
      2    3
     / /   
    7    4  
   /      / 
  8        5
            /
             6

       Test Case 3: add long left branch under 3  (branch : left to the 3   3-> 8 -> 9 -> 10 -> 11

       **/

    Node root = new Node(1); //hd = 0
    // test Case 1 -- output: 2 1 3 6
    root.left = new Node(2); // hd = -1
    root.right = new Node(3); // hd = +1
    root.left.right = new Node(4); // hd = 0
    root.left.right.right = new Node(5); // hd = +1
    root.left.right.right.right = new Node(6); // hd = +2

    // test case 2 -- output: 8 7 2 1 3 6 
    root.left.left = new Node(7); // hd = -2
    root.left.left.left = new Node(8); // hd = -3

    // test case 3 -- output: 11 7 2 1 3 6 
    root.left.left.left = null;
    root.right.left = new Node(8); //hd = 0
    root.right.left.left = new Node(9); // hd = -1
    root.right.left.left.left = new Node(10); // hd = -2
    root.right.left.left.left.left = new Node(11); //hd = -3

    new TreeTopView().topView(root);
  }