Estoy tratando de devolver verdadero si el árbol está equilibrado y falso si no, se me ocurrió esta solución recursiva a continuación, pero no soy correcto con el valor booleano correcto. Siento que tiene sentido comparar la altura más alta del árbol con la altura más baja. No estoy seguro de dónde me estoy equivocando
function tree (rootNode) { // Your code here 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 } }Mi algoritmo recursivo será así.
function isBalanced(rootNode){ if(rootNode == null){ return true; } if(checkHeight(rootNode) === -1){ return false; } else{ return isBalanced(root.left) && isBalanced(root.right); } }y el método auxiliar checkHeight que verificará la altura será
function checkHeight(rootNode){ if(root ==null){ return 0; } let leftHeight=checkHeight(root.left); let rightHeight=checkHeight(root.right); if(Math.abs(leftHeight - rightHeight) > 1){ return -1; } else{ return Math.max(leftHeight,rightHeight) +1; } }NOTA: Este Algo tendrá la complejidad de tiempo de O(N)
El problema principal es que su función está mezclando dos cosas:
Si el propósito final es devolver un booleano, entonces necesita una función diferente para obtener la altura (un número).
En segundo lugar, al determinar la altura, las dos primeras líneas de su código muestran una inconsistencia:
null (vacío) se determina que su altura es 0Sin embargo, estos dos árboles tienen una altura diferente. Si se considera que un solo nodo (raíz) tiene altura 0, entonces un árbol vacío tiene altura -1. Esto está en línea con Wikipedia :
La altura de un nodo es la longitud del camino descendente más largo hasta una hoja desde ese nodo. La altura de la raíz es la altura del árbol. La profundidad de un nodo es la longitud del camino a su raíz (es decir, su camino raíz). Esto suele ser necesario en la manipulación de los diversos árboles autoequilibrados, en particular los árboles AVL. El nodo raíz tiene profundidad cero, los nodos hoja tienen altura cero y un árbol con un solo nodo (por lo tanto, una raíz y una hoja) tiene profundidad y altura cero. Convencionalmente, un árbol vacío (árbol sin nodos, si se permiten) tiene una altura −1.