Categorías
Algorithms

LeetCode – Subárbol BST más grande (Java)

Dado un árbol binario, busque el subárbol más grande, que es un árbol de búsqueda binaria (BST), donde más grande significa subárbol con el mayor número de nodos en él.

Solución Java

class Wrapper{
    int size;
    int lower, upper;
    boolean isBST;
 
    public Wrapper(){
        lower = Integer.MAX_VALUE;
        upper = Integer.MIN_VALUE;
        isBST = false;
        size = 0;
    }
} 
public class Solution {
    public int largestBSTSubtree(TreeNode root) {
        return helper(root).size;
    }
 
    public Wrapper helper(TreeNode node){
        Wrapper curr = new Wrapper();
 
        if(node == null){
            curr.isBST= true;
            return curr;
        }
 
        Wrapper l = helper(node.left);
        Wrapper r = helper(node.right);
 
        //current subtree's boundaries
        curr.lower = Math.min(node.val, l.lower);
        curr.upper = Math.max(node.val, r.upper);
 
        //check left and right subtrees are BST or not
        //check left's upper again current's value and right's lower against current's value
        if(l.isBST && r.isBST && l.upper<=node.val && r.lower>=node.val){
            curr.size = l.size+r.size+1;
            curr.isBST = true;
        }else{
            curr.size = Math.max(l.size, r.size);
            curr.isBST  = false;
        }
 
        return curr;
    }
}

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 *