Encuentre el subárbol BST más grande en un árbol binario dado | conjunto 3

BST más grande en un árbol binario | conjunto 3

Método 3 (más corto, más inteligente y más eficiente) 

En esta sección, se analiza una solución O(n) diferente. Esta solución es más simple que las soluciones discutidas en Set-1 y Set-2 y funciona en tiempo O(n). En este método, no necesitamos verificar explícitamente si el árbol binario es BST. Un árbol es BST si lo siguiente es cierto para cada Node x. 

1. El valor más grande en el subárbol izquierdo (de x) es más pequeño que el valor de x.
2. El valor más pequeño en el subárbol derecho (de x) es mayor que el valor de x.

Entonces, solo verificaremos si el valor más grande del subárbol izquierdo es menor que el valor del Node raíz y el valor más pequeño del subárbol derecho es mayor que el valor del Node raíz.

Usaremos una array/lista ans:

• ans[0]=valor mínimo
• ans[1]=valor máximo
• ans[2]=tamaño del BST más grande actual

Algoritmo:

1. Si raíz==Ninguna:
devuelve INT_MAX,INT_MIN,0
2. Si (raíz.izquierda==Ninguna y raíz.derecha==Ninguna):
             devuelve raíz.datos,raíz.datos,1
3. Inicializar ans=[0 ,0,0]
4. Verifique si el valor más grande del subárbol izquierdo es menor que el valor del Node raíz y el valor más pequeño del subárbol derecho es mayor que el valor del Node raíz, si esto es cierto, actualice el ans en consecuencia y volver ans.
5. Si 4 es falso, asignaremos valores como IMIN,IMAX, max(left[2],right[2] y devolveremos ans.

#User function Template for python3
IMIN = -2147483648
IMAX = 2147483647
def largestBst(root):
        if root==None:
            return IMAX,IMIN,0
        if (root.left==None and root.right==None):
            return root.data,root.data,1
         
        left=largestBst(root.left)
        right=largestBst(root.right)
 
         
        ans=[0,0,0]
         
        if left[1]<root.data and right[0]>root.data:
            ans[0]=min(left[0],right[0],root.data)
            ans[1]=max(right[1],left[1],root.data)
            ans[2]=1+left[2]+right[2]
            return ans
 
        ans[0]=IMIN
        ans[1]=IMAX
        ans[2]=max(left[2],right[2])
        return ans
 
def largestBstUtil(root):
      # Return the size of the largest sub-tree which is also a BST
     return largestBst(root)[2]
     
#  Driver Code Starts
import sys
sys.setrecursionlimit(1000000)
from collections import deque
# Tree Node
class newNode:
    def __init__(self, val):
        self.right = None
        self.data = val
        self.left = None
 
# Driver Code
if __name__ == '__main__':
      
    """Let us construct the following Tree
        50
        / \
        75 45
    /
    40 """
    root = newNode(50)
    root.left = newNode(75)
    root.right = newNode(45)
    root.left.left = newNode(40)
    print("Size of the largest BST is",largestBstUtil(root))

Size of the largest BST is 2

Complejidad de Tiempo: O(n), Espacio Auxiliar: O(n)

Aquí n es el número de Nodes en el árbol binario dado.