Suponiendo que los subárboles de valor único significan que solo hay un valor único sobre todos los nodos en el subárbol, se sigue un algoritmo de tiempo lineal al implementar el siguiente método y luego llamarlo desde la raíz.
- Si este nodo es una hoja, incremente un contador global, anote este nodo como la raíz de un subárbol de valor único y regrese. (Este es el caso base).
- De lo contrario, este nodo no es una hoja. Verifique recursivamente si cada nodo es la raíz de un subárbol de valor único y, además, vea si cada elemento secundario coincide en valor con el nodo actual. Si un solo nodo falla en cualquiera de estas verificaciones, entonces este nodo no es un subárbol de valor único. De lo contrario, es así que incremente el contador global, anote el nodo como la raíz de un subárbol de valor único y regrese.
Esto se ejecuta en tiempo lineal porque cada nodo será el parámetro principal del método recursivo exactamente una vez, y cada nodo, que tiene un padre único, se considera exactamente una vez en el cuerpo del método.
- Cómo recuperarse de una falla en las entrevistas técnicas de rol de TI en el sitio de Google
- ¿Cómo diseñarás una lista de contactos en un teléfono celular? ¿Qué estructura de datos usarás?
- ¿Cuál es el acertijo lógico que Dev Bootcamp pregunta durante su entrevista? ¿Cómo es y cómo puedo prepararme mejor?
- ¿Cuál es la mejor manera de prepararse para las entrevistas de Java para desarrolladores no java?
- ¿Cuáles son los mejores ejemplos de implementación completa de estructuras de datos prominentes usando C (no C ++)?