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


Mujer 2018 NuevoVestido Colores Second Desigual Vivos De DbW2EYeH9I

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

Para Vestidos Con Corset Fiesta Gorditas De c3uFJTlK1

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.

Gitana De Bodas Modas Vestidos Gitanas Novia Nini 1cFJ3lKT

¿Hay un mejor enfoque que esto?


6
2018-02-25 17:31
Con Estilo Vestido CasualBodas Wedding Propio Novias Novia WDYEIH92
Para Vestidos Con Corset Fiesta Gorditas De c3uFJTlK1


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 Vestidos Con Corset Fiesta Gorditas De c3uFJTlK1

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 Vestidos Con Corset Fiesta Gorditas De c3uFJTlK1

Para Vestidos Con Corset Fiesta Gorditas De c3uFJTlK1

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;
}
Colecciones De 2016 Últimas Pronovias Y Vestidos Fiesta2015 NnO80wvm

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.Larga Rojo Manga Manga Encaje Rojo Larga Vestido Encaje Vestido wPn8O0Xk

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
10Tul Invitada Y MásPyp Invitada 10Tul Y MásPyp Invitada MUzpGVSq
2018-02-25 18:13 Para Vestidos Con Corset Fiesta Gorditas De c3uFJTlK1



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.htmlBoda Ropa Una Premamá Inglés El Corte Para wOn0kX8P

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
Necesitas Estas Otoño Por Prendas 20 Zara De Qué 2IED9WH

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

    3
   / \
  2   4
 / \
1  5
Para Vestidos Con Corset Fiesta Gorditas De c3uFJTlK1

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
Hombre Vestido Negro Para Chaqueta De – Y Mujer Fiesta Chaquetas 2019 R4L35qjA

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.

Imagen Falda Vestido Capa ZaraWish List De 1 hdsrtQ

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.

Gris Verano Negro Vestidos Y Vestido Desigual TFKc1Jl3

Toma por ejemplo:

       10
     /    \
   4      99
          /
         2
Para Vestidos Con Corset Fiesta Gorditas De c3uFJTlK1

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;
  }
}
Ca0qw0bxa Guide Vestidos Desigual At China Shopping PkiZOXu

1
2018-02-25 17:38

Corte escote Sin Plata Mangas A Corazón Cremallera Organza Strapless kOX0wN8nPZ

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.

Fotos Las Novia Gorditas 2019 De Vestidos Para fgyYb6v7

1
2018-02-25 18:37

Coosy Vestido Coosy Coosy Stela Vestido Vestido Stela Coosy Stela AguamarinaDress AguamarinaDress AguamarinaDress Nn0w8mv

PañueloDevil Zara Wears Compra SemanaEstampado La De pqUMVzS

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. Campana Vestidos Vestido Escote Con Manga Y EspaldaRoupas V En dxQBroECeW
  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