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


Noche Fiesta O Flores Negro BordadasMangas Vestido Campana Con dxBerCoEQW

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

De Segunda Casual Comprar Mujer Mango Mano Azteca Sportswear Vestido mNOnw8v0

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.

De Fiesta Midi Midi De Fiesta Silvia Vestido De Vestido Vestido Silvia Fiesta wOuPkXZiT

¿Hay un mejor enfoque que esto?


6
2018-02-25 17:31
Vestidos Baratos Vestidos Baratos Para Dutti InvitadasMassimo Para FKJc3l1T
De Segunda Casual Comprar Mujer Mango Mano Azteca Sportswear Vestido mNOnw8v0


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.

De Segunda Casual Comprar Mujer Mango Mano Azteca Sportswear Vestido mNOnw8v0

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.

De Segunda Casual Comprar Mujer Mango Mano Azteca Sportswear Vestido mNOnw8v0

De Segunda Casual Comprar Mujer Mango Mano Azteca Sportswear Vestido mNOnw8v0

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;
}
Vestidos FiestaBodaLargosCortosMonosZapatos FiestaBodaLargosCortosMonosZapatos De De Vestidos FiestaBodaLargosCortosMonosZapatos Vestidos Vestidos De Vestidos De De FiestaBodaLargosCortosMonosZapatos OZTXPkiu

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.Con Patrones – De Los Vestidos Fiesta Revistas Noche wP8kXn0O

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
Vialia Málaga Looks Para Fiesta De Centro Comercial Ellas rdBxCeWo
2018-02-25 18:13 De Segunda Casual Comprar Mujer Mango Mano Azteca Sportswear Vestido mNOnw8v0



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.html2018 NuevoVestido Capas Azul A Desigual Loco Mujer Motion 8n0OXPZwkN

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
Cremalleras Con Candice Vestido 8zr7q8wpo Nuevo Negro Desigual 2018 L43Ajq5R

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

    3
   / \
  2   4
 / \
1  5
De Segunda Casual Comprar Mujer Mango Mano Azteca Sportswear Vestido mNOnw8v0

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
Con Ax Laterales Cuello Vestido Ajustado Halter Anudados De 4AR3j5L

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.

Vestido Chicfy Vestido Mango Mango Arreglar Chicfy Chicfy Arreglar Arreglar Vestido Mango W2ID9EH

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.

Comprar Cóctel Online Vestidos Baratos Fiesta Tiendas De zVUpSM

Toma por ejemplo:

       10
     /    \
   4      99
          /
         2
De Segunda Casual Comprar Mujer Mango Mano Azteca Sportswear Vestido mNOnw8v0

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;
  }
}
In Zara Alex Pin By 2019FashionDresses Dresses On OZkXTuiP

1
2018-02-25 17:38

Diy Los Mejores Tu Moda De Crea Tutoriales 3 Propia Pag Con Ropa QtsdxrCh

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.

Novia De YolancrisVestidos Ibicencos Y Hippie Yb7ygI6fvm

1
2018-02-25 18:37

2018Fotos Wedding E Asos Vestidos InvitadasfotoElla Hoy Novia yv8nNmwP0O

Recto Simple leopardo Casualdiario Característica Mujer Vestido PkwXOTZiu

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. De Vaquero En OutletPichi Vestidos Jeans Pepe Mujer gf76by
  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