Editar: esta es una respuesta larga con muchos lugares para confundirse, ¡así que haga preguntas si no entiende! (eso también significa muchos lugares donde podría haberme equivocado, así que avísame si ves algo mal)
Cuando examiné este problema por primera vez, estaba bastante claro para mí que tendríamos que hacer un preprocesamiento de algún tipo para resolverlo en el tiempo [matemático] O (n) [/ matemático]. Consideré las siguientes opciones para el preprocesamiento:
- Recuperando la profundidad de cada nodo
- Recuperando la lista de nodos, ordenados por profundidad
- Almacenar punteros principales para cada nodo
- Almacenar el número de aristas hasta el descendiente más profundo
(y algunos otros)
- ¿Cómo se debe decidir sobre un clasificador / algoritmo óptimo para usar en un conjunto de datos en particular?
- Cómo establecer un límite máximo y mínimo para una variable entera / flotante en la definición
- ¿Cuál es una manera de ordenar una matriz en C por una entrada simple?
- ¿Cuál es la mejor manera de estudiar la estructura de datos de árbol?
- Cómo generar una lista de todas las permutaciones de una matriz 4 × 4 con solo los números 1, 2, 3 y 4 en Python
Intenté algunos enfoques para mapear el problema en uno diferente (como tomar los nodos en orden de nivel y darme cuenta de que cada ruta desde la raíz a un nodo era una subsecuencia de orden de nivel).
En última instancia, estas exploraciones me llevaron a darme cuenta de una cosa: podríamos determinar el primer nodo en nuestra respuesta en [matemáticas] \ Theta (n) [/ matemáticas] tiempo, pero probablemente tomaría [matemáticas] O (n) [/ matemáticas ] tiempo por nodo para calcular cada nodo sucesivo, a menos que hagamos las cosas de manera diferente. Para obtener un algoritmo [matemático] O (n) [/ matemático], necesitaríamos alguna forma de atravesar el árbol que nos permitiera calcular el rango de cada nodo a medida que avanzábamos sin retroceder.
El rango de cada nodo tendría que ser una función lineal del número de aristas o nodos no visitados por encima, por lo que el rango de los rangos probablemente sería de [matemática] 0 [/ matemática] a [matemática] \ Theta (n) [/ mates]. Por lo tanto, si pudiéramos calcular el rango para cada nodo en el tiempo [matemático] \ Theta (n) [/ matemático], podríamos ordenar los nodos por su rango en el tiempo [matemático] \ Theta (n) [/ matemático] (nosotros haga una matriz de tamaño [matemática] \ Theta (n) [/ matemática], donde la clave es el rango, y el valor es una lista de nodos con esa clasificación, ordenada por algún comparador; luego, iteramos sobre la matriz en orden inverso de rango, generando los valores).
Como ya había investigado varios pasos de preprocesamiento que podría usar, me concentré en la segunda parte: iterar sobre el árbol de una manera significativa para calcular los rangos a medida que avanzaba.
Mi pensamiento inicial fue comenzar en la hoja más profunda e iterar hacia arriba, posiblemente eliminando nodos a medida que avanzaba. Pensé en tal vez compactar el árbol para representar múltiples aristas como una arista ponderada (similar a cómo un árbol radix compacta un árbol). En última instancia, mis investigaciones desde el fondo resultaron infructuosas, y consideré repetir desde la parte superior del árbol hacia abajo, lo que me pareció un poco intuitivo.
Pensé que sería difícil trabajar con un primer recorrido profundo, así que me concentré en atravesar el árbol nivel por nivel usando una cola.
Cuando llegamos a un nodo en un recorrido de nivel por nivel, ¿hay alguna manera de conocer el rango de ese nodo? Bueno, necesitamos saber sobre cualquier borde que ya se haya visitado antes de llegar a un nodo. Si estamos en un nodo dado, ¿podemos determinar fácilmente cuántos bordes que conducen a él serán visitados cuando lleguemos a ese nodo? Realmente no. Sin embargo, se me ocurrió una idea útil: si llegamos a un nodo, y ese nodo tiene un antepasado que tiene hijos que son más profundos que el nodo en el que estamos, los bordes por encima de ese antepasado serán visitados antes de llegar a ese nodo Por ejemplo, considere:
Supongamos que estamos en el nodo F. Observe que F tiene un antepasado C, que tiene hijos cuya profundidad llega a ser inferior a F. Eso significa que al contar la cantidad de aristas a F, no podemos contar las aristas desde la raíz A a C.
Obtener esa información del nodo F resulta ser complicado. Tendríamos que dar marcha atrás en el árbol hasta llegar a un antepasado que tenga hijos más profundos, y luego descontar el número de bordes desde la raíz a ese antepasado. ¿Qué pasaría si, sin embargo, pudiéramos propagar estos datos por el árbol a medida que iteramos a través de él?
Bueno, si estamos haciendo un recorrido de nivel por nivel del árbol, entonces podemos pasar información adicional a cada nodo cuando lo agreguemos a nuestra cola de nodos para visitar. Entonces, ¿qué pasa si cada vez que colocamos en cola un nodo, [math] x [/ math], pasamos a lo largo del número de bordes no visitados por encima? Luego, para cuando lleguemos a cada nodo hoja, podríamos calcular un rango basado en cuántos nodos no visitados están por encima de él.
La parte difícil es determinar cuántos nodos no visitados estarán por encima del siguiente nodo que estamos poniendo en cola. Veamos el gráfico de arriba. Supongamos que actualmente estamos visitando el nodo C y queremos poner en cola a sus hijos, D y E. Cuando ponemos en cola D, tenemos que pasar que hay 1 borde no visitado por encima, y cuando ponemos en cola E, tenemos que pasar que hay 2 bordes no visitados encima de él. El número de aristas no visitadas desde el nodo raíz hacia abajo a través de un nodo [matemáticas] u [/ matemáticas] en el nivel [matemáticas] i [/ matemáticas] a un nodo, [matemáticas] v [/ matemáticas] en el nivel [matemáticas] i + 1 [/ math] será:
[matemáticas] F (v) = [/ matemáticas]
[mates]
1 +
\ begin {cases}
F (u), & \ text {si v se visita antes que sus hermanos} \\\\
0, & \ text {de lo contrario}
\ end {casos}
[/mates]
Analicemos esto. Primero, el número mínimo de aristas no visitadas para cualquier nodo es [matemática] 1 [/ matemática] porque siempre hay una arista única para cada nodo, por lo que cuando lleguemos a un nodo, será la primera vez que visitemos esa arista. Entonces, si nuestro nodo está a lo largo del camino hacia el nodo más profundo (en comparación con los caminos hacia abajo a través de sus hermanos), entonces ese nodo será el primer nodo que atraviesa los nodos ancestrales, por lo que heredará el número completo de bordes no visitados arriba eso. De lo contrario, todos los bordes superiores serán visitados, por lo que no heredarán nada.
Dado que estamos iterando a través del árbol de arriba hacia abajo, siempre calcularemos [matemáticas] F (u) [/ matemáticas] antes de que necesitemos calcular [matemáticas] F (v) [/ matemáticas], así que tenemos Una solución de programación dinámica. Esto tiene sentido ya que los árboles tienden a exhibir una subestructura óptima.
El caso base es que [matemática] F (nodo raíz) = 0 [/ matemática] ya que no hay bordes no visitados sobre el nodo raíz.
La última parte para resolver este problema es encontrar una manera de determinar si un nodo [math] v [/ math] es visitado antes que sus nodos hermanos. Se visita un nodo antes que sus nodos hermanos si el subárbol debajo de él es más profundo que los subárboles debajo de sus hermanos. Aquí es donde el preprocesamiento será útil. En cada nodo, podemos almacenar un puntero al niño cuyos descendientes alcanzan lo más profundo del árbol.
Entonces, ¿cómo hacemos exactamente eso? Bueno, podemos hacer un primer recorrido en profundidad del árbol, pasando la profundidad de cada nodo hacia abajo mientras visitamos a los niños (solo agregue uno a la profundidad del nodo actual). A medida que retrocedemos, comparamos las profundidades máximas que alcanzó cada elemento secundario y su subárbol (si corresponde), y almacenamos un puntero a ese elemento secundario. Luego volvemos con esa profundidad máxima. En el momento en que repetimos todo el camino, podremos saber qué hijo de un nodo tiene un subárbol que se profundiza en el tiempo constante (nota: si dos hijos de un nodo tienen la misma profundidad, consideramos al hijo con el valor entero más bajo como el hijo que llega más profundo; debemos hacer esto para satisfacer el requisito: “En caso de empate, visite la hoja con el número entero más pequeño”).
Lo que esto significa es que podemos calcular [matemáticas] F (v) [/ matemáticas] en tiempo constante, y [matemáticas] F (v) [/ matemáticas] para todas las [matemáticas] v [/ matemáticas] en [matemáticas] \ Theta (n) [/ math] tiempo.
Como se describió anteriormente, utilizamos una matriz de tamaño [math] \ Theta (n) [/ math] para almacenar los rangos de cada nodo hoja (llame a esta matriz [math] ranks [/ math]). Cada vez que calculamos el rango de un nodo hoja (llame a este rango [math] r [/ math]), agregamos el nodo hoja a la lista almacenada en [math] ranks [r] [/ math].
Luego, necesitamos extraer los valores en nuestras listas en orden descendente de rango y orden ascendente de valor dentro del mismo rango. Por lo general, esto requeriría un algoritmo de clasificación de tiempo [matemática] \ Omega (n \ lg n) [/ matemática]. Sin embargo, tenemos algunas garantías que nos permiten sortear este límite.
Es decir, tenemos la garantía de que no tenemos números duplicados, y tenemos la garantía de que el rango de valores se encuentra en [math] \ Theta (n) [/ math].
Primero, iteramos sobre nuestra matriz de rango [matemático] [/ matemático] e iteramos sobre cada valor en la lista para cada rango. Construimos una matriz con el valor como clave y el rango como valor. Esto lleva tiempo [math] \ Theta (n) [/ math].
Mientras iteramos, también construimos otra matriz, con el rango como clave, y el índice inicial en los resultados ordenados es el valor (el rango más alto tiene el índice inicial más bajo). (Esta matriz es similar al histograma de las frecuencias clave en el recuento).
Finalmente, iteramos sobre nuestro rango de valores en orden ascendente. Para cada número, buscamos su rango usando nuestra primera matriz. Luego buscamos el índice inicial para ese rango usando nuestra segunda matriz. Colocamos el número actual en ese índice en nuestra matriz de respuestas, y luego aumentamos el valor del índice inicial para el rango actual.
Para cuando hemos iterado sobre todos los valores, tenemos nuestra respuesta, ordenada según sea necesario en los detalles de la pregunta.
Veamos un ejemplo de ejecución, donde n = 16.
Primero, preprocesamos:
nodo 9: más profundo = (nodo 8, profundidad 2) -> ( nodo 2 , profundidad 5)
-> nodo 8: más profundo = ( nodo 10 , profundidad 2)
——-> nodo 10: más profundo = indefinido
-> nodo 2: más profundo = (nodo 1, profundidad 2) -> ( nodo 0 , profundidad 5)
——-> nodo 1: más profundo = indefinido
——-> nodo 0: más profundo = (nodo 14, profundidad 3) -> ( nodo 15 , profundidad 5)
———–> nodo 14: más profundo = indefinido
———–> nodo 15: más profundo = ( nodo 4 , profundidad 5)
—————> nodo 4: más profundo = ( nodo 3 , profundidad 5)
——————–> nodo 3: más profundo = indefinido
————> nodo 5: más profundo = indefinido
————> nodo 6: más profundo = indefinido
-> nodo 13: más profundo = ( nodo 7 , profundidad 4)
——-> nodo 7: más profundo = ( nodo 11 , profundidad 4)
———–> nodo 11 : más profundo = ( nodo 12 , profundidad 4)
—————> nodo 12 : más profundo = indefinido
Entonces supongo que tenemos eso almacenado en una matriz en algún lugar como:
deepestChild [0] = 15
deepestChild [1] = indefinido
deepestChild [2] = 0
deepestChild [3] = indefinido
deepestChild [4] = 3
deepestChild [5] = indefinido
deepestChild [6] = indefinido
deepestChild [7] = 11
deepestChild [8] = 10
deepestChild [9] = 2
deepestChild [10] = indefinido
deepestChild [11] = 12
deepestChild [12] = indefinido
deepestChild [13] = 7
deepestChild [14] = indefinido
deepestChild [15] = 4
Ahora, veamos el recorrido de nivel por nivel.
Deje X = nodo y E = número de aristas no visitadas por encima de ese nodo
Cola
(X = 9, E = 0) (comience con el nodo raíz, use 0 bordes ancestros no visitados para el caso base)
Dequeue (X = 9) -> get (E = 0)
Poner en cola (X = 8, E = 1 + 0 = 1)
Poner en cola (X = 2, E = 1 + 0 = 1)
Poner en cola (X = 13, E = 1 + 0 = 1)
Cola
(X = 8, E = 1), (X = 2, E = 1), (X = 13, E = 1)
Dequeue (X = 8) -> get (E = 1)
Poner en cola (X = 10, E = 1 + 1 = 2)
Cola
(X = 2, E = 1), (X = 13, E = 1), (X = 10, E = 2)
Dequeue (X = 2) -> get (E = 1)
Poner en cola (X = 1, E = 1 + 0 = 1)
Poner en cola (X = 0, E = 1 + 1 = 2)
Cola
(X = 13, E = 1), (X = 10, E = 2), (X = 1, E = 1), (X = 0, E = 2)
Dequeue (X = 13) -> get (E = 1)
Poner en cola (X = 7, E = 1 + 1 = 2)
Cola
(X = 10, E = 2), (X = 1, E = 1), (X = 0, E = 2), (X = 7, E = 2)
Dequeue (X = 10) -> get (E = 2)
Sin hijos, por lo que el nodo hoja. Rango de tienda [2] = [10].
Cola
(X = 1, E = 1), (X = 0, E = 2), (X = 7, E = 2)
Dequeue (X = 1) -> get (E = 1)
Sin hijos, por lo que el nodo hoja. Rango de tienda [1] = [1]
Cola
(X = 0, E = 2), (X = 7, E = 2)
Dequeue (X = 0) -> get (E = 2)
Poner en cola (X = 14, E = 1 + 0 = 1)
Poner en cola (X = 15, E = 1 + 2 = 3)
Poner en cola (X = 5, E = 1 + 0 = 1)
Poner en cola (X = 6, E = 1 + 0 = 1)
Cola
(X = 7, E = 2), (X = 14, E = 1), (X = 15, E = 3), (X = 5, E = 1), (X = 6, E = 1)
Dequeue (X = 7) -> get (E = 2)
Poner en cola (X = 11, E = 1 + 2 = 3)
Cola
(X = 14, E = 1), (X = 15, E = 3), (X = 5, E = 1), (X = 6, E = 1), (X = 11, E = 3)
Dequeue (X = 14) -> get (E = 1)
Sin hijos, por lo que el nodo hoja. Actualizar rango [1] = [1, 14]
Cola
(X = 15, E = 3), (X = 5, E = 1), (X = 6, E = 1), (X = 11, E = 3)
Dequeue (X = 15) -> get (E = 3)
Poner en cola (X = 4, E = 1 + 3 = 4)
Cola
(X = 5, E = 1), (X = 6, E = 1), (X = 11, E = 3), (X = 4, E = 4)
Dequeue (X = 5) -> get (E = 1)
Sin hijos, por lo que el nodo hoja. Actualizar rango [1] = [1, 14, 5]
Cola
(X = 6, E = 1), (X = 11, E = 3), (X = 4, E = 4)
Dequeue (X = 6) -> get (E = 1)
Sin hijos, por lo que el nodo hoja. Actualizar rango [1] = [1, 14, 5, 6]
Cola
(X = 11, E = 3), (X = 4, E = 4)
Dequeue (X = 11) -> get (E = 3)
Poner en cola (X = 12, E = 1 + 3 = 4)
Cola
(X = 4, E = 4), (X = 12, E = 4)
Dequeue (X = 4) -> get (E = 4)
Poner en cola (X = 3, E = 1 + 4 = 5)
Cola
(X = 12, E = 4), (X = 3, E = 5)
Dequeue (X = 12) -> get (E = 4)
Sin hijos, por lo que el nodo hoja. Actualizar rango [4] = [12]
Cola
(X = 3, E = 5)
Dequeue (X = 3) -> get (E = 5)
Sin hijos, por lo que el nodo hoja. Actualizar rango [5] = [3]
La cola ahora está vacía.
Por ahora, tenemos:
rango [0] = indefinido
rango [1] = [1, 14, 5, 6]
rango [2] = [10]
rango [3] = indefinido
rango [4] = [12]
rango [5] = [3]
rango [6] = indefinido
rango [7] = indefinido
rango [8] = indefinido
rango [9] = indefinido
rango [10] = indefinido
rango [11] = indefinido
rango [12] = indefinido
rango [13] = indefinido
rango [14] = indefinido
rango [15] = indefinido
Ahora, construimos nuestros valores de mapeo de matriz en rangos:
valueToRank [0] = indefinido
valueToRank [1] = 1
valueToRank [2] = indefinido
valueToRank [3] = 5
valueToRank [4] = indefinido
valueToRank [5] = 1
valueToRank [6] = 1
valueToRank [7] = indefinido
valueToRank [8] = indefinido
valueToRank [9] = indefinido
valueToRank [10] = 2
valueToRank [11] = indefinido
valueToRank [12] = 4
valueToRank [13] = indefinido
valueToRank [14] = 1
valueToRank [15] = indefinido
Luego construimos nuestro rango de mapeo de matriz al índice inicial para ese rango:
rankToIndex [0] = indefinido
rankToIndex [1] = 3
rankToIndex [2] = 2
rankToIndex [3] = indefinido
rankToIndex [4] = 1
rankToIndex [5] = 0
rankToIndex [6] = indefinido
rankToIndex [7] = indefinido
rankToIndex [8] = indefinido
rankToIndex [9] = indefinido
rankToIndex [10] = indefinido
rankToIndex [11] = indefinido
rankToIndex [12] = indefinido
rankToIndex [13] = indefinido
rankToIndex [14] = indefinido
rankToIndex [15] = indefinido
Luego iteramos sobre los valores de 0 a [matemática] n – 1 [/ matemática].
0 0
valueToRank [0] = indefinido
Omitir
1
valueToRank [1] = 1
rankToIndex [1] = 3, actualice rankToIndex [1] a 4
respuesta [3] = 1
2
valueToRank [2] = indefinido
Omitir
3
valueToRank [3] = 5
rankToIndex [5] = 0, actualice rankToIndex [5] a 1
respuesta [0] = 3
4 4
valueToRank [4] = indefinido
Omitir
5 5
valueToRank [5] = 1
rankToIndex [1] = 4, actualice rankToIndex [1] a 5
respuesta [4] = 5
6 6
valueToRank [6] = 1
rankToIndex [1] = 5, actualice rankToIndex [1] a 6
respuesta [5] = 6
7 7
valueToRank [7] = indefinido
Omitir
8
valueToRank [8] = sin definir
Omitir
9 9
valueToRank [9] = indefinido
Omitir
10
valueToRank [10] = 2
rankToIndex [2] = 2, actualice rankToIndex [2] a 3
respuesta [2] = 10
11
valueToRank [11] = indefinido
Omitir
12
valueToRank [12] = 4
rankToIndex [4] = 1, actualice rankToIndex [4] a 2
respuesta [1] = 12
13
valueToRank [13] = indefinido
Omitir
14
valueToRank [14] = 1
rankToIndex [1] = 6, actualice rankToIndex [1] a 7
respuesta [6] = 14
15
valueToRank [15] = undefind
Omitir
Responder
[3, 12, 10, 1, 5, 6, 14]
Ahora revisemos esa respuesta:
Parece que funcionó. También funciona para el gráfico en la pregunta original.
Este algoritmo se ejecuta en [matemáticas] \ Theta (n) [/ matemáticas] tiempo y espacio.
Esperemos que funcione para todos los casos … Probablemente me perdí algo 🙂
Código Java (realmente malo, pero aquí en caso de que alguien necesite aclaraciones)
import java.util.*; public class LeafOrder { public static void main(String[] args) { /*********************************************************************\ * Build tree * \*********************************************************************/ final int n = 16; TreeNode[] nodes = new TreeNode[n]; for (int i = 0; i < n; i++) { nodes[i] = new TreeNode(i); } // Level 1 TreeNode root = nodes[9]; // Level 2 root.addChild(nodes[8]); root.addChild(nodes[2]); root.addChild(nodes[13]); // Level 3 nodes[8].addChild(nodes[10]); nodes[2].addChild(nodes[1]); nodes[2].addChild(nodes[0]); nodes[13].addChild(nodes[7]); // Level 4 nodes[0].addChild(nodes[14]); nodes[0].addChild(nodes[15]); nodes[0].addChild(nodes[5]); nodes[0].addChild(nodes[6]); nodes[7].addChild(nodes[11]); // Level 5 nodes[15].addChild(nodes[4]); nodes[11].addChild(nodes[12]); // Level 6 nodes[4].addChild(nodes[3]); /*********************************************************************\ * Preprocessing * \*********************************************************************/ preprocessDeepestReachingChildren(root); /*********************************************************************\ * Level-by-level traversal * \*********************************************************************/ Queue queue = new LinkedList(); queue.offer(new NodeRank(root, 0)); List<List> rank = new ArrayList<List>(n); boolean[] valueIsLeaf = new boolean[n]; int[] valueToRank = new int[n]; int[] rankToIndex = new int[n]; for (int i = 0; i < n; i++) { rank.add(new ArrayList()); } while (!queue.isEmpty()) { NodeRank dequeued = queue.poll(); TreeNode currentNode = dequeued.getNode(); int currentValue = currentNode.getValue(); int currentRank = dequeued.getRank(); ArrayList children = currentNode.getChildren(); TreeNode deepestReachingChild = currentNode.getDeepestReachingChild(); int numChildren = children.size(); if (numChildren == 0) { List rankList = rank.get(currentRank); rankList.add(currentValue); valueToRank[currentValue] = currentRank; valueIsLeaf[currentValue] = true; } for (int i = 0; i = 0; i--) { List rankList = rank.get(i); int rankListSize = rankList.size(); if (rankListSize == 0) { continue; } rankToIndex[i] = currentIndex; currentIndex += rankListSize; } int[] answer = new int[n]; int highestIndexSet = 0; for (int i = 0; i < n; i++) { if (!valueIsLeaf[i]) { continue; } int rankForValue = valueToRank[i]; int indexForRank = rankToIndex[rankForValue]; rankToIndex[rankForValue]++; answer[indexForRank] = i; highestIndexSet = Math.max(highestIndexSet, indexForRank); } /*********************************************************************\ * Outputting answer * \*********************************************************************/ for (int i = 0; i <= highestIndexSet; i++) { System.out.print(answer[i] + ((i != highestIndexSet) ? ", " : "")); } System.out.println(); } public static int preprocessDeepestReachingChildren(TreeNode root) { return preprocessDeepestReachingChildren(root, 0); } public static int preprocessDeepestReachingChildren(TreeNode root, int depth) { int maxDepth = 0; TreeNode maxChild = null; ArrayList children = root.getChildren(); int numChildren = children.size(); if (numChildren == 0) { return depth; } for (int i = 0; i maxDepth || (currentChildDepth == maxDepth && currentChild.getValue() < maxChild.getValue())) { maxDepth = currentChildDepth; maxChild = currentChild; } } root.setDeepestReachingChild(maxChild); return maxDepth; } } class TreeNode { private int value; private ArrayList children; private TreeNode deepestReachingChild; public TreeNode(int nodeValue) { this.value = nodeValue; this.children = new ArrayList(); } public int getValue() { return this.value; } public void addChild(TreeNode child) { this.children.add(child); } public ArrayList getChildren() { return this.children; } public TreeNode getDeepestReachingChild() { return this.deepestReachingChild; } public void setDeepestReachingChild(TreeNode child) { this.deepestReachingChild = child; } } class NodeRank { private TreeNode node; private int rank; public NodeRank(TreeNode node, int rank) { this.node = node; this.rank = rank; } public TreeNode getNode() { return this.node; } public int getRank() { return this.rank; } } Editar: Otra forma de resolver esto si no desea utilizar una cola es hacer un recorrido primero en profundidad después del preprocesamiento. Cada vez que llegas a un nodo, miras a sus hijos y encuentras el que llega más profundo al árbol y es el más pequeño (lo sabemos por preprocesamiento). Recurre hacia abajo a través de ese niño, pasando a lo largo de la profundidad actual + 1. Cuando regrese de la recursión, visite a los otros niños, pasando una profundidad de 0. Cuando llegue a un permiso, almacene su profundidad como su rango.
Ese enfoque se vería así:
import java.util.*; public class LeafOrder { public static void main(String[] args) { /*********************************************************************\ * Build tree * \*********************************************************************/ final int n = 16; TreeNode[] nodes = new TreeNode[n]; for (int i = 0; i < n; i++) { nodes[i] = new TreeNode(i); } // Level 1 TreeNode root = nodes[9]; // Level 2 root.addChild(nodes[8]); root.addChild(nodes[2]); root.addChild(nodes[13]); // Level 3 nodes[8].addChild(nodes[10]); nodes[2].addChild(nodes[1]); nodes[2].addChild(nodes[0]); nodes[13].addChild(nodes[7]); // Level 4 nodes[0].addChild(nodes[14]); nodes[0].addChild(nodes[15]); nodes[0].addChild(nodes[5]); nodes[0].addChild(nodes[6]); nodes[7].addChild(nodes[11]); // Level 5 nodes[15].addChild(nodes[4]); nodes[11].addChild(nodes[12]); // Level 6 nodes[4].addChild(nodes[3]); /*********************************************************************\ * Preprocessing * \*********************************************************************/ List<List> rank = new ArrayList<List>(n); boolean[] valueIsLeaf = new boolean[n]; int[] valueToRank = new int[n]; for (int i = 0; i < n; i++) { rank.add(new ArrayList()); } preprocessDeepestReachingChildren(root); preprocessRanks(root, rank, valueToRank, valueIsLeaf); /*********************************************************************\ * Building answer in sorted order * \*********************************************************************/ int[] rankToIndex = new int[n]; for (int i = n - 1, currentIndex = 0; i >= 0; i--) { List rankList = rank.get(i); int rankListSize = rankList.size(); if (rankListSize == 0) { continue; } rankToIndex[i] = currentIndex; currentIndex += rankListSize; } int[] answer = new int[n]; int highestIndexSet = 0; for (int i = 0; i < n; i++) { if (!valueIsLeaf[i]) { continue; } int rankForValue = valueToRank[i]; int indexForRank = rankToIndex[rankForValue]; rankToIndex[rankForValue]++; answer[indexForRank] = i; highestIndexSet = Math.max(highestIndexSet, indexForRank); } /*********************************************************************\ * Outputting answer * \*********************************************************************/ for (int i = 0; i <= highestIndexSet; i++) { System.out.print(answer[i] + ((i != highestIndexSet) ? ", " : "")); } System.out.println(); } public static int preprocessDeepestReachingChildren(TreeNode root) { return preprocessDeepestReachingChildren(root, 0); } public static int preprocessDeepestReachingChildren(TreeNode root, int depth) { int maxDepth = 0; TreeNode maxChild = null; ArrayList children = root.getChildren(); int numChildren = children.size(); if (numChildren == 0) { return depth; } for (int i = 0; i maxDepth || (currentChildDepth == maxDepth && currentChild.getValue() < maxChild.getValue())) { maxDepth = currentChildDepth; maxChild = currentChild; } } root.setDeepestReachingChild(maxChild); return maxDepth; } public static void preprocessRanks(TreeNode root, List<List> rank, int[] valueToRank, boolean[] valueIsLeaf) { preprocessRanks(root, 0, rank, valueToRank, valueIsLeaf); } public static void preprocessRanks(TreeNode root, int currentRank, List<List> rank, int[] valueToRank, boolean[] valueIsLeaf) { TreeNode deepestReachingChild = root.getDeepestReachingChild(); ArrayList children = root.getChildren(); int numChildren = children.size(); if (numChildren == 0) { int currentValue = root.getValue(); List rankList = rank.get(currentRank); rankList.add(currentValue); valueToRank[currentValue] = currentRank; valueIsLeaf[currentValue] = true; } for (int i = 0; i < numChildren; i++) { TreeNode currentChild = children.get(i); preprocessRanks(currentChild, 1 + ((currentChild == deepestReachingChild) ? currentRank : 0), rank, valueToRank, valueIsLeaf); } } } class TreeNode { private int value; private ArrayList children; private TreeNode deepestReachingChild; public TreeNode(int nodeValue) { this.value = nodeValue; this.children = new ArrayList(); } public int getValue() { return this.value; } public void addChild(TreeNode child) { this.children.add(child); } public ArrayList getChildren() { return this.children; } public TreeNode getDeepestReachingChild() { return this.deepestReachingChild; } public void setDeepestReachingChild(TreeNode child) { this.deepestReachingChild = child; } } class NodeRank { private TreeNode node; private int rank; public NodeRank(TreeNode node, int rank) { this.node = node; this.rank = rank; } public TreeNode getNode() { return this.node; } public int getRank() { return this.rank; } }
