es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

¿Cómo determinar si un árbol binario está balanceado o no usando la recursión?

01 Jun, 2023 Programación

Estoy tratando de devolver “true” si el árbol está equilibrado y “false” si no lo está, pero no estoy obteniendo el booleano correcto con la solución recursiva que he creado a continuación. Siento que tiene sentido comparar la altura más alta del árbol con la altura más baja. ¿No estoy seguro de dónde estoy cometiendo un error?

function tree (rootNode) {
  // Tu código aquí
  if (!rootNode) return 0;
  if (!rootNode.left && !rootNode.right) return 0;
  let minHeigth = 1 + Math.min(tree(rootNode.left), tree(rootNode.right))
  let maxHeigth = 1 + Math.max(tree(rootNode.left), tree(rootNode.right))
  if(maxHeigth - minHeigth <= 1){
    return true
  }else{
    return false
  }
}
Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    La lógica utilizada en la función tree() es casi correcta, pero hay un par de errores en ella. En primer lugar, la función calcula la altura del árbol en lugar de verificar su equilibrio. En segundo lugar, hay un error tipográfico en la variable minHeigth, que debería ser minHeight.

    Para comprobar si un árbol está equilibrado, necesitamos asegurarnos de que la diferencia entre la altura de sus sub-árboles izquierdo y derecho sea como máximo uno. Por lo tanto, para corregir la función, necesitamos reemplazar el cálculo de las alturas mínima y máxima con las comprobaciones de los sub-árboles izquierdo y derecho.

    Aquí está la función corregida:

    function isBalanced(rootNode) {
  // Caso base: el árbol vacío está equilibrado
  if (!rootNode) return true;

  // Verifique si los sub-árboles izquierdo y derecho están equilibrados
  let isLeftBalanced = isBalanced(rootNode.left);
  let isRightBalanced = isBalanced(rootNode.right);

  // Si ambos sub-árboles están equilibrados, compruebe la diferencia de altura
  if (isLeftBalanced && isRightBalanced) {
    let leftHeight = getHeight(rootNode.left);
    let rightHeight = getHeight(rootNode.right);
    let heightDiff = Math.abs(leftHeight - rightHeight);
    return heightDiff <= 1;
  }

  // De lo contrario, el árbol no está equilibrado
  return false;
}

function getHeight(node) {
  if (!node) return 0;
  return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

    La función isBalanced() verifica recursivamente si los sub-árboles izquierdo y derecho del rootNode dado están equilibrados, y si es así, calcula su diferencia de altura utilizando la función getHeight(). Si la diferencia de altura es como máximo uno, la función devuelve true, indicando que el árbol está equilibrado. De lo contrario, devuelve false.

    La función getHeight() calcula la altura de un nodo determinado de manera recursiva agregando uno a la altura máxima de sus sub-árboles izquierdo y derecho. Tenga en cuenta que debemos verificar los nodos null para devolver cero como su altura.

    ¡Espero que esto ayude!

Comments are closed.