Pregunta Encontrar el subárbol más grande en un BST


Que Las Todas En Zara Veremos Vestidos Los Bodas De ucT1lFK3J

Dado un árbol binario, quiero descubrir el subárbol más grande que es una BST en él.

Para Ropa De Con Vestidos Interior Espalda Novia Descubierta v8m0wONn

Enfoque ingenuo:

Tengo en mente un enfoque ingenuo en el que visito cada nodo del árbol y paso este nodo a una función isBST. También mantendré un registro del número de nodos en un subárbol si es un BST.

00 Eur Basic Zara Estrenar The 15 A Vestido En Imperio Corte Por sQdxhrCt

¿Hay un mejor enfoque que esto?


6
2018-02-25 17:31
Hombro Rojo Cremallera Mangas Sin Particular lentejuela Plisado Solo lKJFcT1
Para Ropa De Con Vestidos Interior Espalda Novia Descubierta v8m0wONn


Respuestas:


He publicado la solución completa y la explicación en mi blog:

http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

La idea es hacer un recorrido transversal en profundidad y pasar valores mínimos y máximos de abajo hacia arriba en lugar de arriba hacia abajo En otras palabras, verificamos los nodos más profundos antes de verificar si los nodos anteriores cumplen los requisitos de BST.

Para Ropa De Con Vestidos Interior Espalda Novia Descubierta v8m0wONn

La razón principal de hacer esto es cuando uno de los nodos no satisface las propiedades BST, todos los subárboles anteriores (que también incluye este nodo) deben no satisfacer los requisitos de BST.

Para Ropa De Con Vestidos Interior Espalda Novia Descubierta v8m0wONn

Para Ropa De Con Vestidos Interior Espalda Novia Descubierta v8m0wONn

En comparación con el enfoque de arriba hacia abajo, el enfoque de abajo hacia arriba es una opción tan increíble porque los resultados para el número total de nodos podrían pasarse al árbol. Esto nos evita recalcular una y otra vez. El número total de nodos para un subárbol es simplemente el número total de nodos de sus subárboles izquierdo y derecho más uno.

Este algoritmo se ejecuta en O (N) complejidad de tiempo y O (1) espacio, que es tan eficiente como puede ser. (donde N es la cantidad total de nodos en el árbol binario).

Debajo está el código de C ++ que funciona. La parte difícil de la implementación es cuidar cómo los valores mínimo y máximo se pasan de abajo hacia arriba. Tenga en cuenta que no inicialicé los valores mínimo y máximo a medida que se inicializan en la parte inferior del árbol.

// Find the largest BST subtree in a binary tree.
// If the subtree is a BST, return total number of nodes.
// If the subtree is not a BST, -1 is returned.
int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,
                   int &maxNodes, BinaryTree *& largestBST) {
  if (!p) return 0;
  bool isBST = true;
  int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST);
  int currMin = (leftNodes == 0) ? p->data : min;
  if (leftNodes == -1 ||
     (leftNodes != 0 && p->data <= max))
    isBST = false;
  int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST);
  int currMax = (rightNodes == 0) ? p->data : max;
  if (rightNodes == -1 ||
     (rightNodes != 0 && p->data >= min))
    isBST = false;
  if (isBST) {
    min = currMin;
    max = currMax;
    int totalNodes = leftNodes + rightNodes + 1;
    if (totalNodes > maxNodes) {
      maxNodes = totalNodes;
      largestBST = p;
    }
    return totalNodes;
  } else {
    return -1;   // This subtree is not a BST
  }
}

BinaryTree* findLargestBSTSubtree(BinaryTree *root) {
  BinaryTree *largestBST = NULL;
  int min, max;
  int maxNodes = INT_MIN;   // INT_MIN is defined in <climits>
  findLargestBSTSubtree(root, min, max, maxNodes, largestBST);
  return largestBST;
}
Árabe Vestidos Compre Joya De Novia 2018 Últimos Modesto Musulmanes N80wyvPOnm

2017-11-23 19:59



Supongo que el problema que estás tratando de resolver es encontrar el BST más grande (con más nodos) en BT. En ese caso, deberá atravesar todos los nodos de los árboles para comprobar si se trata de una BST, y una vez que encuentre una, deberá verificar si tiene más nodos que el más grande encontrado hasta el momento.La Rodilla Amazon De Hasta esVestidos Fiesta T3JcKlF1

class TreeNode
{
    public int value;
    public TreeNode left;
    public TreeNode right;
}

void LargestBST(TreeNode bt, IDictionary<TreeNode, bool> isBST, IDictionary<TreeNode, int> nodeCount, ref TreeNode largestBST)
{
    if (bt == null)
        return;
    if (IsBST(bt, isBST) && (largestBST == null || NodeCount(bt, nodeCount) > NodeCount(largestBST, nodeCount)) 
        largestBST = bt;
    else
    {
        LargestBST(bt.left, isBST, nodeCount, ref largestBST);
        LargestBST(bt.Right, isBST, nodeCount, ref largestBST);
    }
}

bool IsBST(TreeNode node, IDictionary<TreeNode, bool> isBST)
{
    if (node == null)
        return true;

    bool result;
    if (!isBST.TryGetValue(node, out result))
    {
        TreeNode maxLeft = Max(node.Left);
        TreeNode minRight = Min(node.Right);
        result = (maxLeft == null || maxLeft.value <= node.value) &&
                 (minRight == null || minRight.value >= node.value) &&
                 IsBST(node.left, isBST) && IsBST(node.Right, isBST);
        isBST.Add(node, result);
    }
    return result;
}

TreeNode Max(TreeNode node)
{
    if (node == null)
        return null;
    while (node.right != null)
        node = node.right;
    return node;
}

TreeNode Min(TreeNode node)
{
    if (node == null)
        return null;
    while (node.left != null)
        node = node.left;
    return node;
}

int NodeCount(TreeNode node, IDictionary<TreeNode, int> nodeCount)
{
    if (node == null)
        return 0;
    int result;
    if (!nodeCount.TryGetValue(node, out result))
    {
        result = 1 + NodeCount(node.left, nodeCount) + NodeCount(node.right, nodeCount);
        nodeCount.Add(node, result);
    }
    return result;
}

7
VestidosVestidos De Y Foto Fiesta Modelo 1Novias 252 E9YDHeW2I
2018-02-25 18:13 Para Ropa De Con Vestidos Interior Espalda Novia Descubierta v8m0wONn



El árbol es una BST si su recorrido en orden le da sus elementos en orden ordenado. Puede usar este código aquí si quiere una implementación de ejemplo: http://placementsindia.blogspot.com/2007/12/c-program-to-check-whether-binary-tree.htmlOtoño By Verano Primavera Y Andy Jeans Pepe Mujer Colección Warhol POuTlXZwki

El tiempo de ejecución es O (N) donde N = número de nodos.

Considerando que el árbol es una BST si los dos subárboles de la raíz son ambas BST es incorrecto (y para la persona que borró su respuesta que propuso esta solución: no debería haber eliminado su respuesta, personalmente no iba a devolvérsela y hay tanto para aprender de una mala, pero aparentemente buena solución como de una buena). Contraejemplo:

    3
   / \
  2   4
 / \
1  5
Vestidos De Rubén Novia Hernández Tendencia 2019La Colección ZuOPkwXTi

Ahora, para obtener el subárbol más grande que es una BST, considere este árbol:

    3
   / \
  2   4
 / \
1  5
Para Ropa De Con Vestidos Interior Espalda Novia Descubierta v8m0wONn

El inorder-transversal es 1 2 5 3 4. Creo que puede resolver su problema original encontrando la subsecuencia contigua ordenada de longitud máxima en el inorder-travelling. Solo debes tener cuidado de no seleccionar secuencias que no describan una BST. Por ejemplo, para:

    10
   / \
  2   14
 / \  |
1  5  20
es Dutti Estampado Seda Vestido Corto Ropamujermoda Massimo – iuwPXlZTOk

El inorder-transversal es 1 2 5 10 20 14. No seleccione 20. Creo que esto se puede lograr asegurándose de descartar elementos siempre que su selección deje de tener sentido. Por ejemplo, cuando llegue a 14, descarte el 20. No estoy seguro si esto se puede hacer eficientemente sin embargo. Editaré mi publicación si encuentro una manera exacta.


2018-02-25 18:01



Creo que podrías evitar comprobar si cada nodo es la raíz de una BST trabajando de arriba hacia abajo en lugar de hacia abajo. Si un subárbol es una BST va a ser más grande que cualquier subárbol en sí mismo, por lo que no es necesario verificar dentro de un subárbol si ha superado la prueba isBST. Luego, solo tiene isBST devuelve el tamaño de un árbol válido y lo almacena junto con un puntero a la raíz del subárbol si necesita poder encontrarlo de nuevo en lugar de saber qué tan grande es el más grande.

L4621c0am Louche E11 Mostaza Informal Rambler Cathleen Vestido qGpSUMLzV

ACTUALIZAR:

Parte del código publicado aquí para verificar si algo es una BST va a fallar en algunos casos, ya que solo están verificando el padre de un nodo.

Kit Harington Ya Han Leslie Casado Rose Y Se TlF3JK1c

Toma por ejemplo:

       10
     /    \
   4      99
          /
         2
Para Ropa De Con Vestidos Interior Espalda Novia Descubierta v8m0wONn

Esta no es una BST válida, (la 2 está fuera de posición con respecto a la 10) pero si no envía un valor mínimo y máximo hacia abajo a través del árbol, lo verificará incorrectamente como válido. Este pseudocódigo lo tiene en cuenta.

main
{
    Verify(root, MIN_VALUE, MAX_VALUE)
}

boolean Verify(node , min, max)
{

 if(node == null)
   return true;

  if(node.value > min &&
     node.value < max &&
     Verify(node.leftchild, min, node.value) &&
     Verify(node.rightchild,node.value,max)
  {
      return true;
  }
  else
  {
      return false;
  }
}
Tuareg Modas Tuareg Tuareg PublicationsFacebook Modas Tuareg Sevilla Sevilla PublicationsFacebook Modas PublicationsFacebook Sevilla ChdrsBtQx

1
2018-02-25 17:38

Encaje Novia Compre Blanco 2019 Encargo Vestidos Por De Marfil 2YWE9DHI

int getMinMaxValue(Node* root, bool isMin)
{
   if (!root)
   {
      // Not real limits...
      return (isMin ? INT_MAX : INT_MIN);
   }
   int leftVal = getMinMaxValue(root->left, isMin);
   int rightVal = getMinMaxValue(root->right, isMin);
   if (isMin)
   {
      return min(root->value, min(leftVal, rightVal));
   }
   else
   {
      return max(root->value, max(leftVal, rightVal));
   }
}

bool isBST(Node* root)
{
   if (!root)
   {
      return true;
   }

   Node* left = root->left;
   Node* right = root->right;

   if (left)
   {
      if (getMinMaxValue(left, false) > root->value)
      {
         return false;
      }
   }

   if (right)
   {
      if (getMinMaxValue(right, true) < root->value)
      {
         return false;
      }
   }

   return isBST(left) && isBST(right);
}

Luego simplemente desciende desde el nodo raíz comprobando si el subárbol es BST, y toma el más grande.

Vestidosfiestagalamodadreesvestidosjuniors Vestidosfiestagalamodadreesvestidosjuniors Vestidosfiestagalamodadreesvestidosjuniors Jessica Vestidosfiestagalamodadreesvestidosjuniors Jessica Jessica Jessica 8mwnN0

1
2018-02-25 18:37

Al Zalando Tall Vestido Espalda De Tubo Trendy Aire Essentials QrEdxeWCBo

Vestidos Vestidos esVikita NiñaRopa Amazon Amazon esVikita W2D9HEIY

Para verificar si un nodo es la raíz de una BST, debemos verificar recursivamente cada uno de los niños izquierdo y derecho. Si comienza desde la raíz, tendrá que repetir todos los hijos antes de poder decidir que la raíz del árbol binario es una BST o no. Por lo tanto, no tiene sentido llamar a "isBST" para cada nodo. Aquí está mi enfoque

  1. Comenzar desde la raíz
  2. Encuentra el máximo de izquierda a derecha
  3. Si no es máximo a la izquierda y a la derecha, regrese "NO BST"
  4. si BST a la izquierda, verifica si es más grande que el máximo hasta ahora. En caso afirmativo guárdelo y devuelva "NOT BST"
  5. Apuesta Sus En Corte Vestidos De Sirena Innovias Por Novia El BxoerCEQWd
  6. si BST a la derecha, verifica si es más grande que el máximo hasta ahora. En caso afirmativo guárdelo y devuelva "NOT BST"
  7. Si izquierda y derecha son BST, hay un nuevo BST con raíz actual como ROOT y con la cantidad de nodos restantes + derecha + 1

Un par de desafíos en hacer este trabajo es almacenar el máximo hasta el momento para el cual utilicé una variable de referencia MaxNumNodes. maxbst withh tiene la raíz de la BST más grande encontrada cuando la función regresa.

public int MaxBST(Node root, int min, int max, ref Node maxbst, 
        ref int MaxNumNodes)
    {
        if (root == null) return 0;

        //Not a BST
        if (root.data < min || root.data > max) return -1;

        //Find Max BST on left
        int left = MaxBST(root.left, min, root.data, ref maxbst, 
                                    ref MaxNumNodes);
        //Find Max BST on right
        int right = MaxBST(root.right, root.data + 1, max, ref maxbst,
                                            ref MaxNumNodes);

        //Case1: -1 from both branches . No BST in both branches
        if (left == -1 && right == -1) return -1;

        //Case2:No BST in left branch , so choose right 
        //See if the BST on right is bigger than seen so far
        if (left == -1)
        {
            if (right> MaxNumNodes)
            {
                MaxNumNodes = right;
                maxbst = root.right;
            }
            return -1;
        }

        //Case3:No BST in right branch , so choose left 
        //See if the BST on left is bigger than seen so far
        if (right == -1)
        {
            if (left > MaxNumNodes)
            {
                MaxNumNodes = left;
                maxbst = root.left;
            }
            return -1;
        }

        //Case4:Both are BST , new max is left BST + right BST
        maxbst = root;
        return left + right + 1;

    }

0
2018-05-02 15:35



Este no es el enfoque más óptimo, pero podría hacer un recorrido inorden del árbol binario y almacenarlo en una matriz y luego encontrar la secuencia creciente más larga contigua, que le dará la BST con la cantidad máxima de nodos. La complejidad sería O(n) para el recorrido y O(n) para la búsqueda, así que todavía va a ser O(n).


0
2018-01-25 14:26



licensed under cc by-sa 3.0 with attribution.
Política de privacidad Contactos