Suma de nodos a una profundidad dada de un árbol binario (representación de cadenas) -- java campo con parsing campo con tree camp codereview Relacionados El problema

Sum of nodes at a given depth of a binary tree (String representation)


1
vote

problema

Español

Dado un árbol binario de enteros y una profundidad, el objetivo es encontrar la suma de todos los valores de nodo a la profundidad en el árbol. La raíz se considera la profundidad 0, y el árbol se administra como una cadena en el formato: [1,2,3]7 . Por ejemplo, [1,2,3]8 debe devolver [1,2,3]9 .

  [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]0  

Me estaba preguntando si había una mejor manera de analizar esto, o si hubiera alguna forma de mejorar la eficiencia? ¿Hay una "mejor solución" conocida para este tipo de problema?

Original en ingles

Given a binary tree of integers and a depth, the goal is to find the sum of all node values at the depth in the tree. The root is considered depth 0, and the tree is given as a string in the format: (<node-value>(<left subtree>)(<right subtree>)). For example, treeLevelSum("(5(42)(-37(28)()))", 1) should return 5.

int treeLevelSum(String tree, int k) {     int sum   = 0;      int depth = 0;     int value = 0;     int sign  = 1;     for (int i = 1; i < tree.length(); i++) {         if (tree.charAt(i) == '(') {             depth += 1;         } else if (tree.charAt(i) == ')') {             sum   += value * sign;             value  = 0;             sign   = 1;             depth -= 1;         } else if (depth == k) {             if (tree.charAt(i) == '-') {                 sign = -1;             } else {                 value = value * 10 + (tree.charAt(i) - '0');             }         }     }      return sum; } 

I was just wondering if there was a better way of parsing this, or if there was any way of improving efficiency? Is there a known "best solution" for this kind of problem?

        
         
         

Lista de respuestas

2
 
vote
vote
La mejor respuesta
 

Lo más probable es que no pueda mejorar demasiado en este enfoque, ya que necesita escanear toda la cadena, y no convierte ningún valor innecesario. Así que como lo veo, hay tres cosas que podría intentar cambiar, pero lo más probable es que no hagan una diferencia, o posiblemente incluso aumenten el tiempo de funcionamiento.

  • Calcula previa a la longitud de la cadena - No estoy muy seguro de cómo Java maneja este, pero en la condición final de su for Loop que realiza tree.length() . Si esta hubiera sido una función costosa, algunos idiomas ejecutarían esta función para cada ejecución a través del bucle, y se beneficiaría de esto que se realiza frente al bucle 9988777665544332 . La longitud de su cadena no va a cambiar en este caso, por lo que debe ser seguro simplemente hacerlo una vez antes del bucle.
  • No use las llamadas repetidas a tree.charAt(i) - En su código, en el peor de los casos, llame tree.charAt(i) 4 veces (al calcular el valor ). Esto podría hacerse fuera del bloque if una vez. Sin embargo, esta función es $ O (1) $, por lo que el beneficio no sería grande.
  • Cambie la extracción de valor : otro cambio que podría hacerse, es cambiar la forma en que extrae el valor. Un enfoque alternativo podría ser que después de detectar la paranthesis de apertura, puede escanear la cadena para la cadena de valor completa , y luego convertirla.

    Esto podría hacerse preservando el índice de inicio de la cadena de valor, busque hasta que presione un nuevo paréntesis, y luego convertir la subcadena directamente en un número. Sin embargo, esto no necesita ser un método más rápido.

No he dado ningún código en esta respuesta, pero creo que está recibiendo las ideas.

Un comentario, aunque en el algoritmo elegido, es que calcula el valor cuando está en la profundidad correcta, pero en realidad no lo usa antes de atravesar a todos los árboles infantiles y luego golpear el paréntesis final. Esto no es un Problema en la especificación actual, pero si cambió para resumir todos los valores en múltiples profundidades, fallaría miserablemente.

Mi comentario final, es que su código se vea limpio y ordenado con buenos nombres. Si cambiaría algo, posiblemente agregaría un poco más de espacio vertical, y algunos comentarios en cuanto a lo que está haciendo el método.

 

Most likely you can't improve too much on this approach, as you do need to scan the entire string, and you don't convert any unneeded values. So as I see it there are three things you could try changing, but most likely they either not make a difference, or possibly even increase running time.

  • Pre-calculate the length of the string xe2x80x93xc2xa0Not quite sure how Java handles this one, but in the end-condition of your for loop you do tree.length(). If this had been a costly function, then some languages would execute this function for each run through the loop, and would benefit from this being done in front of the for loop. The length of your string isn't going to change in this case, so it should be safe to just do it once before the loop.
  • Not using repeated calls to tree.charAt(i) xe2x80x93xc2xa0In your code, in the worst case, you call tree.charAt(i) 4 times (when calculating the value). This could possibly be done outside the if block just once. However, this function is \$O(1)\$, so the benefit wouldn't be large.
  • Change the value extractionxc2xa0xe2x80x93xc2xa0Another change which could be made, is to change the way you extract the value. An alternative approach could be that after detecting the opening paranthesis, you could scan the string for the entire value string, and then convert it.

    This could be done by preserving the start index of the value string, search until you hit a new parenthesis, and then convert the substring directly into a number. However, this doesn't need to be a faster method.

I've given no code in this answer, but I think you're getting the ideas.

One comment though on chosen algorithm, is that you calculate the value when on the correct depth, but you don't actually use it before you've traversed all child trees and then hit the end parenthesis.This isn't a problem in the current specification, but if it changed to sum up all values on multiple depths, it would fail miserably.

My final comment, is that your code does look clean and tidy with good names. If I'd change anything I would possibly add a little more vertical space, and some comments as to what the method is doing.

 
 

Relacionados problema

2  Implementación de árboles de búsqueda de ternarios en Python 3  ( Ternary search tree implementation in python 3 ) 
He implementado un árbol de búsqueda ternario. Funciona bien. Pero si crees que algo necesita mejorarse, dígalo. Este código fue probado en Python 3.7.4. c...

2  Montón Binomial en Java  ( Binomial heap in java ) 
Tengo esta implementación de un montón de binomio que proporciona inserto, disminución de la tecla y el extracto en el tiempo logarítmico. minpriorityqueue...

1  Retire todos los nodos que no se encuentren en ningún camino con suma> = k  ( Remove all nodes which dont lie in any path with sum k ) 
Dado un árbol binario, una ruta completa se define como un camino desde la raíz a una hoja. La suma de todos los nodos en ese camino se define como la suma d...

2  Eliminación de un nodo en un árbol de búsqueda binario  ( Deletion of a node in a binary search tree ) 
Estoy buscando ver si mi implementación del método de eliminación / eliminación en un árbol de búsqueda binario es suficiente, legible y se ejecuta en un tiem...

4  Función abstracta del mapa del árbol  ( Abstract tree map function ) 
Ejercicio 2.31. Resumen tu respuesta Para ejercer 2.30 para producir un Procedimiento Árbol - Mapa con la propiedad. ese árbol cuadrado podría definirs...

4  Eliminar nodos alternativos de una lista vinculada  ( Delete alternate nodes of a linked list ) 
Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4 entonces la salida debe ser 1- & gt; 3. Si la lista vinculada es 1- & gt; 2- & gt; 3- & gt; 4- & gt; 5,...

13  Árbol de búsqueda binaria - C ++  ( Binary search tree c ) 
Estoy implementando varias estructuras de datos en un intento por aprender C ++. A continuación se muestra un árbol de búsqueda binario que he implementado pa...

3  Incrustar un HTML (cadena) generado de un árbol estructurado de árbol  ( Embedding an html string generated from a tree structured json ) 
Cómo hacer insertJson3 FASTER (¿Debería mantener el script compatible con versiones anteriores de IE y otros navegadores)? Problema innerHTML de este ...

11  Patrones compuestos y de visitantes para la funcionalidad de la encuesta basada en árboles en C #  ( Composite and visitor patterns for tree based survey functionality in c ) 
He escrito alguna funcionalidad de encuesta para un proyecto. Básicamente, un formulario de encuesta genérico que se puede componer de secciones y preguntas. ...

12  Codificación de árbol binario  ( Binary tree encoding ) 
Implementé una solución a este desafío de codificación en el código de golf. Tengo experiencia decente con C / C ++, pero ha sido un tiempo desde que los us...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos