Para entender cuál es la misma línea vertical, primero debemos definir distancias horizontales. Si dos nodos tienen la misma Distancia horizontal (HD), entonces están en la misma línea vertical. La idea de HD es simple. HD para la raíz es 0, un borde derecho (borde que se conecta al subárbol derecho) se considera como +1 distancia horizontal y un borde izquierdo se considera como -1 distancia horizontal. Por ejemplo, en el siguiente árbol, HD para el nodo 4 está en -2, HD para el nodo 2 es -1, HD para 5 y 6 es 0 y HD para el nodo 7 es +2.

Ejemplos:

      1
    /   \

   2     3

  / \   / \
  4  5  6  7

El árbol tiene 5 líneas verticales.

Vertical-Line-1 tiene un solo nodo 4

Vertical-Line-2: tiene un solo nodo 2

Línea vertical-3: tiene tres nodos: 1,5,6

Vertical-Line-4: tiene un solo nodo 3

Vertical-Line-5: tiene un solo nodo 7

Ahora para el arbol

        1            
      /    \
    2        3       
   / \      /  \
  4   5    6    7    
 / \           / \
8   9        10   11

Para el árbol anterior, debemos obtener la salida de cada nivel vertical de arriba a abajo, y de izquierda a derecha horizontalmente

8

4

2 9

1 5 6 o 1 6 5 (ya que 6 y 5 están en el mismo nivel vertical, y el mismo HD, el orden no importa en ellos)

3 10

7

11

Una forma de hacerlo es simplemente creando un multimapa de HD, y hacer un recorrido de orden de nivel, y empujar los valores en el índice de HD correspondiente. Hacer esto en forma de orden de nivel garantizará que visitemos de arriba a abajo verticalmente. Luego imprima el Los nodos forman el HD más bajo al HD más alto, lo que nos satisface de izquierda a derecha.

He leído en alguna parte que podemos hacerlo de una mejor manera utilizando el enfoque de la lista de enlaces dobles o algo similar. ¿Alguna ayuda para las personas?