Compruebe si el árbol binario contiene un BST equilibrado de tamaño K

Dado un Árbol Binario y un entero positivo K . La tarea es verificar si el BST balanceado de tamaño K existe en un árbol binario dado o no. Si existe, imprima » Sí»; de lo contrario, imprima » No» .

Ejemplos: 

Input: K = 4,
Below is the given Tree:
         15
       /    \
      10     26
     /  \     / \
    5   12  25  40
           /   /  \
          20  35   50
                 \
                  60
Output: Yes
Explanation: 
Subtree of the given tree with
size k is given below:
        40
       /  \
      35   50
             \
             60

Input: K = 4,
Below is the given Tree:
            18
            /  
           9    
          / \
         7   10
Output: No
Explanation:
There is no subtree of size K
which forms a balanced BT.

Enfoque: La idea es utilizar Post Order Traversal . Los siguientes son los pasos para resolver el problema: 

  1. Realice un Post Order Traversal en el árbol dado y verifique la condición BST para cada Node donde el valor más grande en el subárbol izquierdo debe ser menor que el valor actual y el valor más pequeño en el subárbol derecho debe ser mayor que el valor actual.
  2. Luego verifique si el BST está equilibrado o no, es decir, la diferencia absoluta entre el subárbol izquierdo y derecho debe ser 0 o 1 .
  3. Luego, pase los valores que regresan de los subárboles al padre.
  4. Realice los pasos anteriores para todos los Nodes y tome la variable booleana ans , que inicialmente se marca como falsa y se usa para verificar si hay un BST equilibrado o no.
  5. Si se encuentra un BST equilibrado de tamaño K , imprima «Sí» , de lo contrario, imprima «No» .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// A tree node
struct node {
    int data;
    node* left;
    node* right;
};
 
// Structure of temporary variable
struct minMax {
    bool isBST;
    bool balanced;
    int size;
    int height;
    int min;
    int max;
};
 
// Function to create the node
node* createNode(int value)
{
    node* temp = new node();
    temp->left = NULL;
    temp->right = NULL;
    temp->data = value;
}
 
// Utility function to find Balanced
// BST of size k
minMax findBalancedBstUtil(node* root,
                           int k, bool& ans)
{
    // Base condition
    if (root == NULL)
        return { true, true, 0, 0,
                 INT_MAX, INT_MIN };
 
    // Temporary variable
    minMax temp;
 
    // Recursive call for left sub-tree
    minMax lsTree
        = findBalancedBstUtil(root->left,
                              k, ans);
 
    if (ans == true)
        return temp;
 
    // Recursive call for right sub-tree
    minMax rsTree
        = findBalancedBstUtil(root->right,
                              k, ans);
 
    if (ans == true)
        return temp;
 
    // Check those conditions which
    // violated the rules of BST
    if (!lsTree.isBST || !rsTree.isBST
        || lsTree.max > root->data
        || rsTree.min < root->data) {
        temp.isBST = false;
        return temp;
    }
 
    // Check whether the Bst is
    // height balanced or not
    if (abs(lsTree.height
            - rsTree.height)
            == 1
        || abs(lsTree.height
               - rsTree.height)
               == 0)
 
        temp.balanced = true;
 
    else
        temp.balanced = false;
 
    // Make the variable true
    // as sub-tree is BST
    temp.isBST = true;
 
    // Store the size
    temp.size = 1 + lsTree.size
                + rsTree.size;
 
    // Store the height
    temp.height = max(lsTree.height,
                     rsTree.height)
                 + 1;
 
    // Store the minimum of BST
    temp.min = root->left != NULL
                   ? lsTree.min
                   : root->data;
 
    // Store the maximum of BST
    temp.max = root->right != NULL
                   ? rsTree.max
                   : root->data;
 
    // Condition to check whether the
    // size of Balanced BST is K or not
    if (temp.balanced == true
        && temp.size == k) {
        ans = true;
    }
 
    // Return the temporary variable
    // with updated data
    return temp;
}
 
// Function to find the Balanced
// BST of size k
string findBalancedBst(node* root,
                       int k)
{
    bool ans = false;
 
    // Utility function call
    findBalancedBstUtil(root, k, ans);
    return ans == true ? "Yes" : "No";
}
 
// Driver Code
int main()
{
    // Given Binary Tree
    node* root = createNode(15);
    root->left = createNode(10);
    root->right = createNode(26);
    root->left->left = createNode(5);
    root->left->right = createNode(12);
    root->right->left = createNode(25);
    root->right->left->left = createNode(20);
    root->right->right = createNode(40);
    root->right->right->left = createNode(35);
    root->right->right->right = createNode(50);
    root->right->right->right->right = createNode(60);
 
    int k = 4;
 
    // Function Call
    cout << findBalancedBst(root, k);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static boolean ans;
 
// A tree node
static class node
{
    int data;
    node left;
    node right;
};
 
// Structure of temporary variable
static class minMax
{
    boolean isBST;
    boolean balanced;
    int size;
    int height;
    int min;
    int max;
     
    public minMax(boolean isBST, boolean balanced,
                  int size, int height, int min,
                  int max)
    {
        super();
        this.isBST = isBST;
        this.balanced = balanced;
        this.size = size;
        this.height = height;
        this.min = min;
        this.max = max;
    }
    public minMax()
    {
        // TODO Auto-generated constructor stub
    }
};
 
// Function to create the node
static node createNode(int value)
{
    node temp = new node();
    temp.left = null;
    temp.right = null;
    temp.data = value;
    return temp;
}
 
// Utility function to find Balanced
// BST of size k
static minMax findBalancedBstUtil(node root,
                                  int k)
{
     
    // Base condition
    if (root == null)
        return new minMax(true, true, 0, 0,
                          Integer.MAX_VALUE,
                          Integer.MIN_VALUE );
 
    // Temporary variable
    minMax temp = new minMax();
 
    // Recursive call for left sub-tree
    minMax lsTree = findBalancedBstUtil(root.left,
                                        k);
 
    if (ans == true)
        return temp;
 
    // Recursive call for right sub-tree
    minMax rsTree = findBalancedBstUtil(root.right,
                                        k);
 
    if (ans == true)
        return temp;
 
    // Check those conditions which
    // violated the rules of BST
    if (!lsTree.isBST || !rsTree.isBST ||
         lsTree.max > root.data ||
         rsTree.min < root.data)
    {
        temp.isBST = false;
        return temp;
    }
 
    // Check whether the Bst is
    // height balanced or not
    if (Math.abs(lsTree.height -
                 rsTree.height) == 1 ||
        Math.abs(lsTree.height -
                 rsTree.height) == 0)
        temp.balanced = true;
         
    else
        temp.balanced = false;
 
    // Make the variable true
    // as sub-tree is BST
    temp.isBST = true;
 
    // Store the size
    temp.size = 1 + lsTree.size +
                    rsTree.size;
 
    // Store the height
    temp.height = Math.max(lsTree.height,
                          rsTree.height) + 1;
 
    // Store the minimum of BST
    temp.min = root.left != null ?
               lsTree.min : root.data;
 
    // Store the maximum of BST
    temp.max = root.right != null ?
               rsTree.max : root.data;
 
    // Condition to check whether the
    // size of Balanced BST is K or not
    if (temp.balanced == true &&
            temp.size == k)
    {
        ans = true;
    }
 
    // Return the temporary variable
    // with updated data
    return temp;
}
 
// Function to find the Balanced
// BST of size k
static String findBalancedBst(node root,
                              int k)
{
    ans = false;
 
    // Utility function call
    findBalancedBstUtil(root, k);
    return ans == true ? "Yes" : "No";
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given Binary Tree
    node root = createNode(15);
    root.left = createNode(10);
    root.right = createNode(26);
    root.left.left = createNode(5);
    root.left.right = createNode(12);
    root.right.left = createNode(25);
    root.right.left.left = createNode(20);
    root.right.right = createNode(40);
    root.right.right.left = createNode(35);
    root.right.right.right = createNode(50);
    root.right.right.right.right = createNode(60);
 
    int k = 4;
 
    // Function call
    System.out.print(findBalancedBst(root, k));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
import sys
 
ans = False
 
# A tree node
class createNode:
     
    def __init__(self, data):
         
        self.data = data
        self.left = None
        self.right = None
 
# Structure of temporary variable
class newMinMax:
     
    def __init__(self, isBST, balanced, size,
                 height, mn, mx):
                      
        self.isBST = isBST
        self.balanced = balanced
        self.size = size
        self.height = height
        self.mn = mn
        self.mx = mx
 
# Utility function to find Balanced
# BST of size k
def findBalancedBstUtil(root, k):
     
    global ans
     
    # Base condition
    if (root == None):
        return newMinMax(True, True, 0, 0,
                         sys.maxsize,
                        -sys.maxsize - 1)
 
    # Temporary variable
    temp = newMinMax(True, True, 0, 0,
                     sys.maxsize,
                    -sys.maxsize - 1)
 
    # Recursive call for left sub-tree
    lsTree = findBalancedBstUtil(root.left, k)
 
    if (ans == True):
        return temp
 
    # Recursive call for right sub-tree
    rsTree = findBalancedBstUtil(root.right, k)
 
    if (ans == True):
        return temp
 
    # Check those conditions which
    # violated the rules of BST
    if (lsTree.isBST == False or
        rsTree.isBST == False or
        lsTree.mx > root.data or
        rsTree.mn < root.data):
        temp.isBST = False
        return temp
 
    # Check whether the Bst is
    # height balanced or not
    if (abs(lsTree.height - rsTree.height) == 1 or
        abs(lsTree.height - rsTree.height) == 0):
        temp.balanced = True
    else:
        temp.balanced = False
 
    # Make the variable true
    # as sub-tree is BST
    temp.isBST = True
 
    # Store the size
    temp.size = 1 + lsTree.size + rsTree.size
 
    # Store the height
    temp.height  = max(lsTree.height ,
                       rsTree.height) + 1
 
    # Store the minimum of BST
    if root.left != None:
        temp.mn = lsTree.mn
    else:
        temp.mn = root.data
 
    # Store the maximum of BST
    if root.right != None:
        temp.mx = rsTree.mx
    else:
        temp.mx = root.data
 
    # Condition to check whether the
    # size of Balanced BST is K or not
    if (temp.balanced == True and
        temp.size == k):
        ans = True
 
    # Return the temporary variable
    # with updated data
    return temp
 
# Function to find the Balanced
# BST of size k
def findBalancedBst(root, k):
     
    global ans
     
    # Utility function call
    findBalancedBstUtil(root, k)
    if ans == True:
        return "Yes"
    else:
        return "No"
 
# Driver Code
if __name__ == '__main__':
     
    # Given Binary Tree
    root = createNode(15)
    root.left = createNode(10)
    root.right = createNode(26)
    root.left.left = createNode(5)
    root.left.right = createNode(12)
    root.right.left = createNode(25)
    root.right.left.left = createNode(20)
    root.right.right = createNode(40)
    root.right.right.left = createNode(35)
    root.right.right.right = createNode(50)
    root.right.right.right.right = createNode(60)
 
    k = 4
 
    # Function Call
    print(findBalancedBst(root, k))
 
# This code is contributed by ipg2016107

C#

// C# program for the
// above approach
using System;
class GFG{
     
static bool ans;
 
// A tree node
public class node
{
  public int data;
  public node left;
  public node right;
};
 
// Structure of temporary
// variable
public class minMax
{
  public bool isBST;
  public bool balanced;
  public int size;
  public int height;
  public int min;
  public int max;   
  public minMax(bool isBST, bool balanced,
                int size, int height, int min,
                int max)
  {
    this.isBST = isBST;
    this.balanced = balanced;
    this.size = size;
    this.height = height;
    this.min = min;
    this.max = max;
  }
   
  public minMax()
  {
    // TODO Auto-generated constructor stub
  }
};
 
// Function to create the node
static node createNode(int value)
{
  node temp = new node();
  temp.left = null;
  temp.right = null;
  temp.data = value;
  return temp;
}
 
// Utility function to find Balanced
// BST of size k
static minMax findBalancedBstUtil(node root,
                                  int k)
{
  // Base condition
  if (root == null)
    return new minMax(true, true, 0, 0,
                      int.MaxValue,
                      int.MinValue);
 
  // Temporary variable
  minMax temp = new minMax();
 
  // Recursive call for left sub-tree
  minMax lsTree =
         findBalancedBstUtil(root.left, k);
 
  if (ans == true)
    return temp;
 
  // Recursive call for right sub-tree
  minMax rsTree =
         findBalancedBstUtil(root.right, k);
 
  if (ans == true)
    return temp;
 
  // Check those conditions which
  // violated the rules of BST
  if (!lsTree.isBST || !rsTree.isBST ||
      lsTree.max > root.data ||
      rsTree.min < root.data)
  {
    temp.isBST = false;
    return temp;
  }
 
  // Check whether the Bst is
  // height balanced or not
  if (Math.Abs(lsTree.height -
               rsTree.height) == 1 ||
      Math.Abs(lsTree.height -
               rsTree.height) == 0)
    temp.balanced = true;
 
  else
    temp.balanced = false;
 
  // Make the variable true
  // as sub-tree is BST
  temp.isBST = true;
 
  // Store the size
  temp.size = 1 + lsTree.size +
                  rsTree.size;
 
  // Store the height
  temp.height = Math.Max(lsTree.height,
                        rsTree.height) + 1;
 
  // Store the minimum of BST
  temp.min = root.left != null ?
             lsTree.min : root.data;
 
  // Store the maximum of BST
  temp.max = root.right != null ?
             rsTree.max : root.data;
 
  // Condition to check whether the
  // size of Balanced BST is K or not
  if (temp.balanced == true &&
      temp.size == k)
  {
    ans = true;
  }
 
  // Return the temporary
  // variable with updated data
  return temp;
}
 
// Function to find the Balanced
// BST of size k
static String findBalancedBst(node root,
                              int k)
{
  ans = false;
 
  // Utility function call
  findBalancedBstUtil(root, k);
  return ans == true ? "Yes" : "No";
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given Binary Tree
  node root = createNode(15);
  root.left = createNode(10);
  root.right = createNode(26);
  root.left.left = createNode(5);
  root.left.right = createNode(12);
  root.right.left = createNode(25);
  root.right.left.left = createNode(20);
  root.right.right = createNode(40);
  root.right.right.left = createNode(35);
  root.right.right.right = createNode(50);
  root.right.right.right.right = createNode(60);
 
  int k = 4;
 
  // Function call
  Console.Write(findBalancedBst(root, k));
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
    // Javascript program for the above approach
    let ans = false;
     
    // A tree Node
    class node
    {
        constructor(value) {
           this.left = null;
           this.right = null;
           this.data = value;
        }
    }
     
    // Structure of temporary variable
    class minMax
    {
        constructor(isBST, balanced, size, height, min, max)
        {
               this.isBST = isBST;
            this.balanced = balanced;
            this.size = size;
            this.height = height;
            this.min = min;
            this.max = max;
        }
    }
     
    // Function to create the node
    function createNode(value)
    {
        let temp = new node(value);
        return temp;
    }
 
    // Utility function to find Balanced
    // BST of size k
    function findBalancedBstUtil(root, k)
    {
 
        // Base condition
        if (root == null)
            return new minMax(true, true, 0, 0,
                              Number.MAX_VALUE,
                              Number.MIN_VALUE );
 
        // Temporary variable
        let temp = new minMax();
 
        // Recursive call for left sub-tree
        let lsTree = findBalancedBstUtil(root.left,
                                            k);
 
        if (ans == true)
            return temp;
 
        // Recursive call for right sub-tree
        let rsTree = findBalancedBstUtil(root.right,
                                            k);
 
        if (ans == true)
            return temp;
 
        // Check those conditions which
        // violated the rules of BST
        if (!lsTree.isBST || !rsTree.isBST ||
             lsTree.max > root.data ||
             rsTree.min < root.data)
        {
            temp.isBST = false;
            return temp;
        }
 
        // Check whether the Bst is
        // height balanced or not
        if (Math.abs(lsTree.height -
                     rsTree.height) == 1 ||
            Math.abs(lsTree.height -
                     rsTree.height) == 0)
            temp.balanced = true;
 
        else
            temp.balanced = false;
 
        // Make the variable true
        // as sub-tree is BST
        temp.isBST = true;
 
        // Store the size
        temp.size = 1 + lsTree.size +
                        rsTree.size;
 
        // Store the height
        temp.height = Math.max(lsTree.height,
                              rsTree.height) + 1;
 
        // Store the minimum of BST
        temp.min = root.left != null ?
                   lsTree.min : root.data;
 
        // Store the maximum of BST
        temp.max = root.right != null ?
                   rsTree.max : root.data;
 
        // Condition to check whether the
        // size of Balanced BST is K or not
        if (temp.balanced == true &&
                temp.size == k)
        {
            ans = true;
        }
 
        // Return the temporary variable
        // with updated data
        return temp;
    }
 
    // Function to find the Balanced
    // BST of size k
    function findBalancedBst(root, k)
    {
        ans = false;
 
        // Utility function call
        findBalancedBstUtil(root, k);
        return ans == true ? "Yes" : "No";
    }
     
    // Given Binary Tree
    let root = createNode(15);
    root.left = createNode(10);
    root.right = createNode(26);
    root.left.left = createNode(5);
    root.left.right = createNode(12);
    root.right.left = createNode(25);
    root.right.left.left = createNode(20);
    root.right.right = createNode(40);
    root.right.right.left = createNode(35);
    root.right.right.right = createNode(50);
    root.right.right.right.right = createNode(60);
  
    let k = 4;
  
    // Function call
    document.write(findBalancedBst(root, k));
  
 // This code is contributed by mukesh07.
</script>
Producción: 

Yes

 

Complejidad temporal: O(N)  
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *