Categorías
Algorithms

LeetCode – Validar árbol de búsqueda binaria (Java)

Dado un árbol binario, determine si es un árbol de búsqueda binario válido (BST).

Suponga que una BST se define de la siguiente manera:

  • El subárbol izquierdo de un nodo contiene solo nodos con claves menores que la clave del nodo.
  • El subárbol derecho de un nodo contiene solo nodos con claves mayores que la clave del nodo.
  • Tanto los subárboles izquierdo como derecho también deben ser árboles de búsqueda binarios.

Solución Java 1: recursivo

Todos los valores del subárbol izquierdo deben ser menores que el padre y el padre del padre, y todos los valores del subárbol derecho deben ser mayores que el padre y el padre del padre. Entonces solo verificamos los límites de cada nodo.

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);    
}
 
public boolean isValidBST(TreeNode p, double min, double max){
    if(p==null) 
        return true;
 
    if(p.val <= min || p.val >= max)
        return false;
 
    return isValidBST(p.left, min, p.val) && isValidBST(p.right, p.val, max);
}

Esta solución también va primero al subárbol izquierdo. Si la violación ocurre cerca de la raíz pero en el subárbol derecho, el método aún cuesta tiempo O (n) y espacio O (h).

La siguiente solución puede manejar violaciones cercanas al nodo raíz más rápidamente.

  LeetCode: distancia más corta desde todos los edificios (Java)
public boolean isValidBST(TreeNode root) {
    return helper(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
}
 
public boolean helper(TreeNode root, double min, double max){
    if(root==null){
        return true;
    }
 
    if(root.val<=min||root.val>=max){
        return false;
    }
 
    boolean isLeftBST = helper(root.left, min, root.val);
    boolean isRightBST = helper(root.right, root.val, max);
 
    if(!isLeftBST||!isRightBST){
        return false;
    }    
 
    return true;
}

Solución Java 2: iterativa

public class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null)
            return true;
 
        LinkedList<BNode> queue = new LinkedList<BNode>();
        queue.add(new BNode(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY));
        while(!queue.isEmpty()){
            BNode b = queue.poll();
            if(b.n.val <= b.left || b.n.val >=b.right){
                return false;
            }
            if(b.n.left!=null){
                queue.offer(new BNode(b.n.left, b.left, b.n.val));
            }
            if(b.n.right!=null){
                queue.offer(new BNode(b.n.right, b.n.val, b.right));
            }
        }
        return true;
    }
}
//define a BNode class with TreeNode and it's boundaries
class BNode{
    TreeNode n;
    double left;
    double right;
    public BNode(TreeNode n, double left, double right){
        this.n = n;
        this.left = left;
        this.right = right;
    }
}
  LeetCode - Serializar y deserializar árbol binario (Java)

El tiempo y el espacio son ambos O (n).

Solución Java 3: recorrido en orden

Dado que el recorrido en orden de BST es ascendente, podemos verificar la secuencia. El tiempo es O (n) y el espacio es O (h). h es la altura de la pila que es la altura del árbol.

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *